Skirmish Maps - Number of Players

[elexis]

34 minutes ago, wowgetoffyourcellphone said:

IMHO, as an aside, regular walls should be remodeled to be standard lengths

The ingame wallbuilding changes the size so as to adapt to the playerchosen area to cover. There are small medium and long wallpieces, and any length is achieved by hiding excess wall length inside the turrets. I guess you know that already. The problem is that it sometimes looks odd? It should be possible to adapt the length numbers in the templates to not get ugly results. If one only uses fixed length pieces, it won't be possible to wall off some passages. It might even result in not being able to close a circle if there would be no adaptation. So if they sometimes look ugly, I think it should be possible to use better numbers, so that the ingame wall placement algorithm can chose 3 medium wall pieces that look better than 4 short ones for instance. Or what's the issue that needs remodeling?

2 hours ago, (-_-) said:

Even if a tile is divided to 4 sub-tiles. the high-res grids can only be used if they are restricted to the area where they are needed. A bunch of high-res grids of the whole map would probably be impossible (oom).

I forgot the OOM. That was the reason we support mapsize 512 (giant) and not 1024.

You are right that one could avoid initializing a grid for the entire map, but only allocate memory for the parts of the map that were written too. The problem is that it map authors probably need to be able to create something the the high res grid and then refer to that grid later on. So one can't discard the grids automatically after a single processing step. Using Binary_space_partitioning one could access the high-res-grid areas with good performance. However partial grids won't save much if the the majority of the map area uses these grids. Map authors could deallocate the grids if they don't need it anymore, but a solution that doesn't require these additional steps would be easier to handle.

I recall the alternative was just storing all entity shapes, which could be extended to include visual actor shapes. The RandomMap object already has a list of entities stored and can easily lookup the obstruction sizes of the few templates used by the map. With BSP one could do the collision tests quickly. Actually we don't want to test for obstruction collisions but want to mark arbitrary areas on the map with a tag (tileclass), but that could still be solved by storing area formulas instead of rasterizing them.... At least for rectangles and disks that would work, but not really for paths, meh. Perhaps these grids could be eh compressed with lzma...dunno...

[wowgetoffyourcellphone]

Just now, elexis said:

The ingame wallbuilding changes the size so as to adapt to the playerchosen area to cover. There are small medium and long wallpieces, and any length is achieved by hiding excess wall length inside the turrets. I guess you know that already. The problem is that it sometimes looks odd? It should be possible to adapt the length numbers in the templates to not get ugly results. If one only uses fixed length pieces, it won't be possible to wall off some passages. It might even result in not being able to close a circle if there would be no adaptation. So if they sometimes look ugly, I think it should be possible to use better numbers, so that the ingame wall placement algorithm can chose 3 medium wall pieces that look better than 4 short ones for instance. Or what's the issue that needs remodeling?

I think when wall lengths are "hidden" or overlap within turrets, man-made walls then cannot be extended to/from those turrets. But I just think as a general good idea to make them standard lengths.

[elexis]

14 minutes ago, wowgetoffyourcellphone said:

I think when wall lengths are "hidden" or overlap within turrets, man-made walls then cannot be extended to/from those turrets. But I just think as a general good idea to make them standard lengths.

Well, the wall placer choses closest wall piece length (small / medium / long) and the excess length is hidden inside the turrets, no other means of hiding that I'm aware of.

Pretty sure one can extend from every turret,  @Hannibal_Barca  has perfected his skills of placing walls in places that noone expects to be buildable and can perhaps post an exemplary screenshot.

How would the mechanism work with standard lengths? Just no hiding inside wallpiece lengths? I wouldn't be surprised if that's already possible with the templates, @s0600204 was the last one to work with these wall templates in vanilla and might know. But the problem is that if there is literally no adaptation, that players might not be able to seal off their walls. Consider an area that has the length 10 meter / feet / bananas, but wall piece lengths are fixed to size 4. Then you can either cover 8 or 12 meters / feet / bananas. If there is some terrain obstruction at 12, one won't be able to close the wall off at all. And walls are only effective if units can't walk past them. Even if there are no obstructions anywhere and the player only wants to create one ring of walls, the last piece might not fit perfectly and thus remain open. If you don't mean to remove adaptation of wall piece lengths, I don't know what you mean. At least in some cases I agree, two wall turrets very close together looks ugly (can also break the balancing).

39 minutes ago, elexis said:

I forgot the OOM. That was the reason we support mapsize 512 (giant) and not 1024. 

@vladislavbelov We were discussing a random map generation problem in the post above. Currently we have a mapsize² grid, that's up to (512 tiles)² and realized using an array containing a JS typed array (u8 I think). (1024)² already gives out of memory errors, that's why 0 A.D. mapsize is limited to 512. The purpose of the grid is to remember an arbitrary area, for example all water on the map, or all forests. The problem is we need to increase the resolution of the grid if we want higher quality random maps that look as good as on this screenshot. And we need one grid for every information to remember (one grid for water, one grid for trees, ...). The area can be arbitrary, so it uses rasterization (for example paths are very random). So we can't store the shapes.

So do you perhaps have a recommendation how to store a rasterized area with as few memory as possible without too much performance loss?

In many cases, the area will only be a small subset of the map area (only 10% of the map have paths), but in other cases, it may be a lot (30% of the map being forest). I thought about BSP to improve lookup times, but I'm not sure how we can save memory when working with so many high resolution grids?

[vladislavbelov]

17 hours ago, elexis said:

@vladislavbelov We were discussing a random map generation problem in the post above. Currently we have a mapsize² grid, that's up to (512 tiles)² and realized using an array containing a JS typed array (u8 I think). (1024)² already gives out of memory errors, that's why 0 A.D. mapsize is limited to 512. The purpose of the grid is to remember an arbitrary area, for example all water on the map, or all forests. The problem is we need to increase the resolution of the grid if we want higher quality random maps that look as good as on this screenshot. And we need one grid for every information to remember (one grid for water, one grid for trees, ...). The area can be arbitrary, so it uses rasterization (for example paths are very random). So we can't store the shapes.

So do you perhaps have a recommendation how to store a rasterized area with as few memory as possible without too much performance loss?

In many cases, the area will only be a small subset of the map area (only 10% of the map have paths), but in other cases, it may be a lot (30% of the map being forest). I thought about BSP to improve lookup times, but I'm not sure how we can save memory when working with so many high resolution grids?

I suppose that the first OOM happens because of JS. Also I think you don't need to increase the heightmap resolution, but the texture map resolution. It's possible, but it requires a lot. Because you need to store this information, but the compression is limited. Possible solutions:

• Megatexture technique (Sparse Virtual Textures). It still requires to store the whole texture (on disk). Also modern OpenGL (3.3+) is needed for an efficient application.
• Mixture textures or blend textures (a more possible solution for us and similar to Oblivion AFAIK). It requires a space too. We may use our terrain patches and limit a max number of textures per patch to 4 and use an RGBA texture to mix them. Now a quality of paths depends on these textures sizes. For example: 1024 map = 64 x 64 patches, let assume that the resolution is 4 pixels per patch cell (pretty small for smooth details) = 64x64 pixels per patch, 64MB without compression in total for the whole map. A bigger resolution requires a lot more because of square. Also you’re able to store an additional texture as an interpolation configurator to decrease the main texture.
• Prepared patterns, it's similar to the previous one, but we don't allow a full flexibility of mixture textures. We suggest prepared mixture textures and map makers use them by their indices. Or they add some by themself (but it requires a bit more space). It allows to use 32x32 (1024 patterns per 1024x1024 texture) or 64x64 (256 patterns per 1024x1024 texture) pattern textures per cell.
• Paths (it's like vector for rasterized pictures), it's good until we have a lot of paths. Its performance depends on number of paths.
• 2D sparse voxel based terrain rendering, it's pretty similar to the megatexture but in terms of vertices and geometry instead of textures. So I think megatextures are preferred here.

These solutions that I remember and shouldn't be hard to map makers. From a superficial look, the third solution looks pretty fine, not much space, not much performance losts. Very likely there're other solutions, but I need time to think and analyze them.

[Hannibal_Barca]

Not sure if this is what is expected of me but here

[elexis]

1 minute ago, vladislavbelov said:

I think you don't need to increase the heightmap resolution, but the texture map resolution. It's possible, but it requires a lot.

You misunderstood me: Not the heightmap, nor the texture map. TileClasses. They rasterize arbitrary areas.

For example the area of all water on the map, the area of all forests on the map, the area of player 1's initial territory on the map, the area of all paths, the area of a gaia city, or whatever area the mapper defines on his map.

The random map script author can use these areas (TileClasses) to determine where to place entities and so forth.

It uses rasterization to represent the area, basically a bool 2D array.

The code must be 100x faster and 16x less memory consuming if we want to place entities as close as on LordGoods screenshot using rasterization.

nani proposes a performance improvement for that in D1637, but I don't know if we can't use something else than a 2D bool array. We might want to continue that discussion at the revision proposal.

5 hours ago, vladislavbelov said:

Prepared patterns

That could work for the entities too. Assemble entities / actors in Atlas, save as XML, load from random map script. Thus no need to higher resoluted bool 2D array.

5 hours ago, vladislavbelov said:

2D sparse voxel

That would be good for some shapes, but bad for many others. Imagine a checkboard map where 50% is part of the area, 50% not part of the area (for example  bush and grass actors).

Describing that area without rasterization sounds extremely bad for memory, no? Even if only 25% of the map has this checkboard pattern.

[Guest]

I think I proposed something which would cut a whole u16 size^2 array.

[vladislavbelov]

2 minutes ago, elexis said:

You misunderstood me: Not the heightmap, nor the texture map. TileClasses. They rasterize arbitrary areas.

For example the area of all water on the map, the area of all forests on the map, the area of player 1's initial territory on the map, the area of all paths, the area of a gaia city, or whatever area the mapper defines on his map.

Do you want to draw on terrain or only to place entities?

5 minutes ago, elexis said:

The random map script author can use these areas (TileClasses) to determine where to place entities and so forth.

It uses rasterization to represent the area, basically a bool 2D array.

The code must be 100x faster and 16x less memory consuming if we want to place entities as close as on LordGoods screenshot using rasterization.

nani proposes a performance improvement for that in D1637, but I don't know if we can't use something else than a 2D bool array. We might want to continue that discussion at the revision proposal.

I think sparse tree isn't bad to place entities, but I'm not sure. Also I already suggested many times to use brushes in JS and do not use heightmaps or direct modifications. I think processing brushes on C++ side may give a speedup.

2 minutes ago, elexis said:

Describing that area without rasterization sounds extremely bad for memory, no? Even if only 25% of the map has this checkboard pattern.

It depends on area. I think it's worse for our case .

[Stan`]

13 minutes ago, elexis said:

That could work for the entities too. Assemble entities / actors in Atlas, save as XML,

One could serialize copy paste. Here is what is put in memory when copy pasting actors

<?xml version="1.0" encoding="UTF-8"?>

<Entities>
	<Entity>
		<Template>structures/maur_civil_centre</Template>
		<Player>1</Player>
		<Position x="212.32877" z="625.73713"/>
		<Orientation y="2.35621"/>
		<ActorSeed>5395</ActorSeed>
	</Entity>
</Entities>

 

[elexis]

1 minute ago, vladislavbelov said:

Do you want to draw on terrain or only to place entities?

Terrain would be good but not necessary. The paths on this screenshot are actor entities.

Entities, we need the information to place Entities. Look at the fence, field, bushes. Placement must be 2-4x more precise than the tilegrid.

9 minutes ago, vladislavbelov said:

I think sparse tree isn't bad to place entities, but I'm not sure.

Good for few large entities yes. But bad to describe 10.000 trees or 40.000 bushes! It looks like this:

Black = tiny bush / tree

White = empty

Sparse tree would consume like 5-10x more memory than a raster grid for this case.

And we need bushes / actors everywhere, on the whole map.

[vladislavbelov]

Just now, elexis said:

Good for few large entities yes. But bad to describe 10.000 trees or 40.000 bushes! It looks like this:

Black = tiny bush / tree

White = empty

Raster maps inside sparse trees

[elexis]

Hill
Cliff
Desert
FertileLand
Water
IrrigationCanal
Passage
Player
BaseResource
Food
Forest
Rock
Metal
Treasure
City
Path
PathStatues
PathCrossing
Statue
Wall
Gate
Road
TriggerPointCityPath
TriggerPointMap
Soldier
Tower
Fortress
Temple
RitualPlace
Pyramid
House
Blacksmith
Stable
ElephantStables
CivicCenter
Barracks
BlemmyeCamp
NubaVillage
Market
Decorative

Consider the most complex random map in a23 (jebel_barkal):

These are 40 rasterized areas.

• The building grids are necessary to control distances between buildings (houses close, fortresses far apart). For few buildings it makes sense to store the polygon.
• For water and paths, spare voxels might make sense.
• But for Decorative (bushes, actors), there is the chessboard situation and we need rasterization for something like the entire map.

So we can save probably 40x as much memory. But spare voxels and polygons are slower than rasterization, no? Random maps already consume 30 seconds or more, we can't make it 16 times slower.

So the only performance optimization possible would be optimizing rasterization, i.e. what to do with D1637, maybe use C++ magic for 2D bool arrays?

The only other performance improvement I can think of is making the maps smarter (less checks) instead of improving the library.

6 hours ago, vladislavbelov said:

I suppose that the first OOM happens because of JS

Actually I didn't check whether the OOM really comes from TileClass bool 2D arrays or whether there aren't many parts in pyrogenesis that fail with mapsize >= 1024.

(But if we increase the resolution of TileClass grids by a factor of 16 to create LordGood grade maps, it would be better to not make mapgen 16 times slower and not 16x as much memory, when it already is too slow.)

[elexis]

59 minutes ago, (-_-) said:

I think I proposed something which would cut a whole u16 size^2 array.

Removing RangeOp definitely sounds like getting rid of a lot of ballast. I'm sure we can get a factor 8x or something if we remove all library bottlenecks and silly code we find. But if we use the approach to increase the grid resolution by a factor of 16, we still need to see if we can go beyond an array of a native-type array proposed in D1637. I guess one should dive into implementation (commit removals, find most significant bottlenecks), but if we had some theory to make TileClass grids 16x faster, we would have the knowledge that LordGoods screenshots would be implementable using higher resoluted grids.

Perhaps one could also get away without using higher resoluted grids, or only using them for a local area. Consider the bush|path|fence|field screenshot again. We don't want to hardcode that a bush is placed every 1m parallel to the path, because thats too regular and looks unnatural. We want random placement constrained to specific distances to other areas. It sounds like we only need the high-resolution check in close proximity, and can use the low-resolution check for distances greater than 1.

I'm reminded of another performance improvement idea I had: The performance degenerates drastically depending on the the distances to tileclasses in the constraints: avoidClasses(clWater, 0) finishes instantly, whereas avoidClasses(clWater, 40) is terribly slow. But if we know in advance that there is only a check against distance 40, then we can paint the water and extend that area by 40 tiles, so that avoidClasses(clWater, 40) can finish instantly too.

Stuff like that. It seems code is a vampiric lifeform that thrives of developer lifetime.

54 minutes ago, stanislas69 said:

One could serialize copy paste. Here is what is put in memory when copy pasting actors

Yes, that's exactly the XML I meant. I'm not sure what you mean with serialization copy paste, but XML is a form of serialization of the entities, and loading XML is a form of deserialization to load them. The code to parse Atlas XML files is already present in C++, only need to expose it to JS. We did the same for Atlas PMP files last release.

[Guest]

Why remove rangeOP?

The only reason I could think of why the other method was added is the older SM. It is faster in all cases.

I did not propose to remove rangeOP. I proposed unifying the texture grids.

Edited April 1, 2019 by Guest

[Stan`]

7 hours ago, elexis said:

Yes, that's exactly the XML I meant. I'm not sure what you mean with serialization copy paste, but XML is a form of serialization of the entities, and loading XML is a form of deserialization to load them. The code to parse Atlas XML files is already present in C++, only need to expose it to JS. We did the same for Atlas PMP files last release.

In one of my old games, one was able to save pastes and load them at another time on another map. So serialising the clipboard into the disk

[Guest]

JS pureness sounds like a moot point to me. Terrain generation is not simple. It is computationally intensive and scales badly with size. There is only so much you can optimize the code until you run into the limitations of using an interpreted language. In fact, the basic blocks of rmgen (createArea etc) can be moved back to C++. But that would end up being a big mistake as the thousands of interface conversions would make it much slower in some cases. But a tileclass is different. I actually see no point in keeping them in JS.

The very first rmgen written by matei was a standalone executable. It was not integrated into the engine AFAK. And then historic_bruno ported the whole thing to JS. And here we are.

(Matei mentioned an ascii generator in his commit. In some basic games, I have seen procedural terrain generation done using ascii characters. Could be that. Don’t know, the only source of information for things that old is commit logs.)

[Stan`]

33 minutes ago, (-_-) said:

. Could be that. Don’t know, the only source of information for things that old is commit logs.

We might have more information on the staff forums and on the meetinglogs @elexis is digging out

[Guest]

On 4/1/2019 at 3:31 AM, elexis said:

Actually I didn't check whether the OOM really comes from TileClass bool 2D arrays or whether there aren't many parts in pyrogenesis that fail with mapsize >= 1024.

 

It doesn’t have to be 1024. Can run into the  issue on any size given enough entities and tileclasses. (Removing that one TODO may help, but thats no fix. Thats just throwing more memory at it)

Edited April 4, 2019 by Guest

[WhiteTreePaladin]

17 hours ago, (-_-) said:

The very first rmgen written by matei was a standalone executable. It was not integrated into the engine AFAK. And then historic_bruno ported the whole thing to JS. And here we are.

16 hours ago, stanislas69 said:

We might have more information on the staff forums and on the meetinglogs @elexis is digging out

@elexis

I remember that there was discussion of this at the time it was converted to JS, and they did take performance into account. (I know there was a cost, but I think that it wasn't considered a bottleneck at the time.) @historic_bruno would definitely be a good one to ask.

[elexis]

That must have been under the assumption of creating maps like we used to (players, one river, random hills, random resources, voila). That were 200-300 lines of code. Now we have 1500 lines or whatnot and the ceiling to map quality is the performance bottleneck. The next barrier to tear down in particular is being able to work with a precision smaller than 1 tile, so that maps can look as good as on those screenshots.

[Guest]

I guess that  is the discussion you were talking about. Read that thread multiple times already.

[Guest]

On 4/1/2019 at 4:07 AM, elexis said:

The performance degenerates drastically depending on the the distances to tileclasses in the constraints

To qoute matei who was the original author:

Quote

...and to efficiently find whether any tiles in the class are within distance D of a point (this will take O(D log D) time).

I don't know how I feel about the algorithm remaining the *exact* same way 14 years later. Tileclasses and the avoid at distance stuff was committed on Sep 4, 2005.

The thing i do know is that random map performance is unacceptable as is. Making it somehow more efficient or just throwing faster execution speed at it are the options here.

On 4/5/2019 at 6:14 AM, elexis said:

The next barrier to tear down in particular is being able to work with a precision smaller than 1 tile, so that maps can look as good as on those screenshots.

I do not agree with that. The next barrier is making it waaay more faster. An ambitious and maybe unachievable goal is to make random maps generate as quickly as AoE2's maps. (if you haven't seen a map script from that game, it follows pretty much the same design (posting an actual map script here is copyright infringment?, but if you got the game locally, you can extract them using Philip's tool written before his 0AD days). Place functions with constraints like 40 away from player or whatever. Obviously I have no idea what the underlying design of the stuff that make it possible is.)

[elexis]

Sure, we can't increase the precision without increasing the performance.

[Guest]

Not necessarily. Over the years, very inefficient code had been added to rmgen. One can always do something and let others down the road deal with the consequences.

But, yes. Faster maps is a requirement for nicer maps.

[elexis]

 

1 hour ago, (-_-) said:

Over the years, very inefficient code had been added to rmgen

Predominant slow code I found was code that either relied on retries when it had more information available before (i.e. unnecessary calls, using createAreasByAreas instead of createAreas, and constraints that are too often unmet), large distances to tileclasses (large area checked) and the Clump/Chain/Path placers algorithms being slow when creating complex patterns.

The other problem is maps becoming increasingly complex, more calls overall. I.e. no more bottlenecks, but 60 individual map script statements that can be reduced from 1s to 0.3s each, i.e. very dull work and in the end it only improves the performance for this one map.

1 hour ago, (-_-) said:

One can always do something and let others down the road deal with the consequences

It says a lot and nothing at the same time.