Random Maps!

[historic_bruno]

I've had a go at getting the random map system into a more usable state, including porting it over to Javascript. Any ideas on the shortcomings, bugs, etc, of the old rmgen can go here, as I've not had much experience with it. I'm sure the basic algorithms need work though.

Right now I've modified the MapReader with some new methods for "Loading" a random map, which is basically like loading a scenario, except there's some extra data associated with it from game setup (map size, random seed, base terrain, etc) and of course a random map script (RMS).

For now a new MapGenerator class is used to handle the details of loading JS libraries for all the necessary classes in their own context, executing the random map script, which then returns some data. This is not progressively loaded yet, so it may be that the RMS will need to be split into multiple functions, registered with the engine and then called piece by piece.

The returned data is a list of entities, a list of textures, a heightmap, a list of tiles, an environment object, and a camera object (since it's not unforeseeable that an RMS may alter the environment and camera). The MapReader parses this data from JS into the respective C++ structures and inits everything just like it would for a scenario. The map format is the current version, not the older one used by rmgen. This much works perfectly.

So the part that needs the most work IMO is an analysis of the algorithmic complexity of the generator, and some decisions on how high or low-level to make the RMS interface.

Re: SpiderMonkey's typed arrays, I don't think the implementation is complete in our version because all I get is "undefined" when I access a typed array. Maybe the constructor API has changed or something.

Edited October 25, 2010 by historic_bruno

[Matei]

Hi Bruno,

Jason forwarded me this link. I wrote the old rmgen (in source/tools/rmgen), so I'd be glad to answer any questions you have about it. I like the idea of integrating it with the main game engine. Right now there are some parts that are C++, but the system is intended to let you write scripts in JS. The parts that are in C++ are mostly that way for performance (e.g. Perlin noise is fairly computationally intensive). However, performance might be good enough with pure JS code, in which case it would certainly be nice to move everything to JS.

[Matei]

I should add: the best way to contact me is to email me at matei@eecs.berkeley.edu, but you can remind me to post here as well.

[Ykkrosh]

Sounds nifty . That implementation approach seems sensible to me. I know nothing at all about actually writing RMS scripts, so I can't say anything useful on that - hopefully there's plenty of people with RMS experience in other RTS games who could suggest what'd be good.

The map format is the current version

Where does the map format get involved? Do you actually generate XML/PMP files and then load them in? (It sounded more like everything was loaded from the JS data structures, not via an intermediate file format, in which case I'm not sure how the map format is part of it.)

This is not progressively loaded yet, so it may be that the RMS will need to be split into multiple functions, registered with the engine and then called piece by piece.

Progressive loading sounds like unpleasant complexity here - RMSs will often be written or modified by inexperienced users, so I'd probably be happier to keep the script control flow as simple as possible. If it takes a non-negligible amount of time, we could perhaps run it in a separate thread to avoid freezing the progress bar.

(Incidentally, if you're not doing this already, the RMS should probably be run it its own unique ScriptInterface (not the simulation's one), so it has independent RNG state etc and so there's no danger of unexpectedly influencing the simulation state. Then we could move it to a new thread without any chance of upsetting SpiderMonkey.)

The parts that are in C++ are mostly that way for performance (e.g. Perlin noise is fairly computationally intensive). However, performance might be good enough with pure JS code, in which case it would certainly be nice to move everything to JS.

Yeah, SpiderMonkey nowadays is hugely faster than when we started, so I'd expect performance to be fine. If not, we could publish our slow code as a JS benchmark and let the SpiderMonkey developers optimise their engine for us

Moving the C++ code into JS seems to have a lot of benefits - it'll be more secure (less chance of e.g. buffer overflows when running untrusted RMS scripts), less buggy (less chance of e.g. GC errors), simpler (we can avoid the complex JS/C++ object bridging code), more flexible, etc, so I think it's worthwhile.

(Also I've thought for a while that having a web-based environment to run RMSs would be quite nice - it'd be a quick way for people to develop new maps without the bother of running or even installing the game. If most of the RMS system is already rewritten into JS, then we can emulate the C++ engine API (just rendering the map as a 2D top-down view of the world or something) and it may not be too hard...)

[historic_bruno]

Where does the map format get involved? Do you actually generate XML/PMP files and then load them in? (It sounded more like everything was loaded from the JS data structures, not via an intermediate file format, in which case I'm not sure how the map format is part of it.)

Right, it's all passed to the engine as fairly simple JS data as described above. I thought this was more sensible than having to generate a PMP/XML first, because the MapReader already has all the logic for parsing maps anyway, so it's not too hard to get it to parse JS data too (I wrote a few FromJSVal overloads to handle things like an Entity struct and u16 vectors).

The nice thing is the game setup hardly needed to be modified at all, because functions like "LoadMapSettings" don't really care where their data comes from as long as it's in the correct form. Instead of parsing JSON from an XML, it can use an entry from the game attributes.

Progressive loading sounds like unpleasant complexity here - RMSs will often be written or modified by inexperienced users, so I'd probably be happier to keep the script control flow as simple as possible. If it takes a non-negligible amount of time, we could perhaps run it in a separate thread to avoid freezing the progress bar.

That was my concern, the loading screen does lock up, but in my test so far it goes very slow (see below).

(Incidentally, if you're not doing this already, the RMS should probably be run it its own unique ScriptInterface (not the simulation's one), so it has independent RNG state etc and so there's no danger of unexpectedly influencing the simulation state. Then we could move it to a new thread without any chance of upsetting SpiderMonkey.)

The MapGenerator class does use its own ScriptInterface, and it's the only part that evals the scripts

Yeah, SpiderMonkey nowadays is hugely faster than when we started, so I'd expect performance to be fine. If not, we could publish our slow code as a JS benchmark and let the SpiderMonkey developers optimise their engine for us

Well so far, using the "Cantabrian Highlands" RMS as a baseline, it's really slow. Until we're certain of why, though, I wouldn't necessarily blame it on SpiderMonkey. Being able to do profiling would help.

Also, it turns out typed arrays do work. I was trying to make a 2D typed array which is silly - the "outer" array has to be a standard Array always, the "inner" array is not a primitive type On the other hand, they don't test as valid arrays using the jsapi macros, so it doesn't work if I try to convert them to a vector As a temporary work-around I copy the typed arrays to standard Arrays before passing them back to the engine.

[Ykkrosh]

You could possibly see if JS execution speed is the issue by uncommenting JSOPTION_JIT in ScriptInterface.cpp (it was disabled since we haven't needed the speed yet, and there's less chance of hitting bugs when not using the JIT).

Profiling C++ is usually easy with e.g. Valgrind's callgrind tool (on Linux); I'm not aware of any decent tools for JS, other than writing explicit timer code to figure out what's slow, or using the F11 in-game profiler (which should record JS function call times when running in Debug mode, but might not be easy to use in this case).

For typed arrays, I guess we should do something like this (using the not-quite-public-but-not-really-private APIs from jstypedarray.h) in ScriptInterface::FromJSVal<std::vector<u32> > and similar overloads, to specialise them for the appropriate typed array type.

[historic_bruno]

Jason forwarded me this link. I wrote the old rmgen (in source/tools/rmgen), so I'd be glad to answer any questions you have about it. I like the idea of integrating it with the main game engine. Right now there are some parts that are C++, but the system is intended to let you write scripts in JS. The parts that are in C++ are mostly that way for performance (e.g. Perlin noise is fairly computationally intensive). However, performance might be good enough with pure JS code, in which case it would certainly be nice to move everything to JS.

Hello, Matei If you don't mind, I'll ask some questions, but anyone else is welcome to jump in if they have some ideas.

Is rmgen fast enough to generate a map, like Cantabrian Highlands in a matter of seconds - reasonable for use in the engine? (I can't get it to run on my system, maybe due to building with VC++ 2008).

I'd like to know some details of "RangeOp" as it doesn't have any coments in the code, but I guess at least it has something to do with counting points within a certain distance of another point. The reason I ask about this is that I've used the "Cantabrian Highlands" script as a sort of baseline to see how JS can handle the random map generation. It's very slow, but especially parts that create areas, which rely most heavily on RangeOp (for tile class constraints).

As an example, to create 3 small lakes on a 2 player map w/ 208 tile size, the inner loop of RangeOp.get() is called over 1 million times! That's a big deal in a JS implementation, moreso because RangeOp uses integer division, which doesn't exist in JavaScript, so every step is floating point and then has to be rounded down. Does 1 million ops sound consistent with the original design, or maybe I implemented something incorrectly in JS?

Also, if I'm not mistaken, the tile class constraints are handled separately. So say we wanted to avoid player, hill, and water classes - to place a forest or something. That would mean 4 separate constraint checks (also avoiding forests) for every point in the area, and that for every forest we wanted to place. That gets complex in a hurry.

What do you think of the feasibility of maintaining the tile classes in one data structure, which gets checked once for a given subset of tile classes? I'm not an expert on spatial data structures, but the following seems logical:

1. Get a "map" with subset of tile classes necessary for our constraints (this gets maintained as new areas are added)

2. Find open areas (i.e. where all constraints pass) which are big enough to fit our new area. Maybe they can be sorted by size, making this part fast?

3. Choose an open area at random (maybe the smallest?) and create new area somewhere within it's bounds.

What I'm thinking is rather than these algorithms dealing with points, they should deal with "areas," which are arbitrary shapes, possibly approximated as rectangles or circles. We could adjust how "strict" to make the constraints, so maybe areas could overlap in some instances.

I'd very much appreciate any advice you can give

Edited October 28, 2010 by historic_bruno

[historic_bruno]

You could possibly see if JS execution speed is the issue by uncommenting JSOPTION_JIT in ScriptInterface.cpp (it was disabled since we haven't needed the speed yet, and there's less chance of hitting bugs when not using the JIT).

Didn't notice any difference with JIT enabled

For typed arrays, I guess we should do something like this (using the not-quite-public-but-not-really-private APIs from jstypedarray.h) in ScriptInterface::FromJSVal<std::vector<u32> > and similar overloads, to specialise them for the appropriate typed array type.

I think that's worth looking in to, although for now the time it takes to return the data and for the engine to parse it is negligible compared to actually generating the map (using typed arrays or not, again seems to have little impact).

[Ykkrosh]

Didn't notice any difference with JIT enabled

Hmm, it ought to make a significant difference if it's working (it should inline all the stuff in inner loops and it sounds like that's the bottleneck here) so I guess something is stopping it from working (the tracing JIT is apparently quite fragile and will fail if things aren't set up exactly right). If you have a runnable patch some time I'd be interested in playing with it to see how to take advantage of the JIT.

(I can't get it to run on my system, maybe due to building with VC++ 2008)

There's a binaries/system/rmgen.exe in SVN so you should be able to simply run that version, I think.

[historic_bruno]

There's a binaries/system/rmgen.exe in SVN so you should be able to simply run that version, I think.

I get an "Application not configured properly" error when I try to run that one. Which may be some sort of VS redistributable library issue, but I've got all thee DLLs installed on my computer and copied into the binaries/systems directory.

I did finally get the one I built in VS2008 to work. Turns out it's a manifest problem, I guess it needs both VS 9.0 and 8.0 run time libraries to run the upgraded project, but the manifest only had 9.0 listed.

Performance is good, it takes 6 seconds to run the Cantabrian highlands script, which includes generating the binary data and XML. Compare that with about 2 minutes to run the JavaScript version... Now I'm curious as to why there's such a disparity

[historic_bruno]

It occurred to me that since all the scripts are in JavaScript, why not use a web browser to profile them?

Here's some profiling results using FireBug in FireFox 3.6.11 - so it's not identical to our Spidermonkey, but it's not far off performance-wise. I wanted to try Firefox 4.0, but FireBug won't install on it yet.

mapgen_profile_firefox3.6.11.pdf

The optimized version replaces some of the Math library functions with alternatives, instead of Math.floor() there's a hack which uses bitwise OR for typecasting a number to an integer. Judging by the fact that these optimizations cut the run time by about 40%, I'd say that's significant. It also looks like optimization is very poor because that's the sort of thing that should be in-lined (Imagine 25 million calls to a given library function, taking up almost 1/4 of the total time to generate the map!)

Note: Since Firefox 3.x doesn't support typed arrays, I had to write a wrapper function which basically creates an untyped Array, all values set to 0. This raises an interesting point. In JavaScript the for...in statement can be used to iterate an array, skipping undefined values. For sparse data, it may be more efficient to create an untyped Array than a typed array, if we only need to iterate over the assigned values. This would require some logic modification, but it's one aspect of the language that may be useful.

Edited October 28, 2010 by historic_bruno

[Ykkrosh]

Firebug disables the JIT, so its measurements are pretty meaningless (at least once the game's able to use the JIT properly). (The SpiderMonkey developers have some plans to make their debugger API compatible with JIT, but I don't think they've even started implementing that yet.)

About RangeOp: Hmm, looks like that's mostly used by TileClass::countInRadius. If the tile sets are usually very sparse, it could possibly be much more efficient if implemented as a quadtree; or it could test distance to clumps rather than to individual tiles, or maybe it could precompute some kind of influence map, or something. Probably lots of ways to optimise it

[historic_bruno]

Firebug disables the JIT, so its measurements are pretty meaningless (at least once the game's able to use the JIT properly). (The SpiderMonkey developers have some plans to make their debugger API compatible with JIT, but I don't think they've even started implementing that yet.)

Ah, I didn't notice that critical little detail. So running the optimized code takes more like 22 seconds in FF 3.6 with FireBug disabled (JIT enabled) That does tell us that JIT is clearly not working for us in Spidermonkey... but it gives me hope that we can in fact write the whole map generator in JS

About RangeOp: Hmm, looks like that's mostly used by TileClass::countInRadius. If the tile sets are usually very sparse, it could possibly be much more efficient if implemented as a quadtree; or it could test distance to clumps rather than to individual tiles, or maybe it could precompute some kind of influence map, or something. Probably lots of ways to optimise it

I think this will be a necessary step, especially if we want to have some kind of integrated web-based editor. The more efficiently it can do this, the better, so it can scale to larger, more complex maps.

Other RMSs may use multidimensional noise maps to construct terrain, along with clump placement, I'll be curious to see how they perform.

Edited October 28, 2010 by historic_bruno

[historic_bruno]

Ran the same test scripts in FF 4 beta 6 using typed arrays, and it's lightning fast... under 4 seconds start to finish, and I validated the output so it's working fine. That's faster than rmgen, although it doesn't have to write any data to disk at the end. Guess that helps put to bed the question of whether JS is fast enough to do random map generation... Now to harness that power in 0 A.D

[Matei]

Sorry for the late reply, it took me a bit of time to page this back in. RangeOp is actually a data structure that is meant to store an array of counts in an efficient manner. In particular, suppose you had the following problem:

* You have an array A of integers of size N.

* You need to quickly query it for sums of the values on ranges of the form i..j (so you want A + ... + A[j]).

* You want to be able to add or subtract from the values at any spot in the array.

RangeOp lets you do this in O(log N) time for each operation. In particular, RangeOp maintains a number of smaller arrays: the big array of size N, then an array of size N/2 that contains sums of groups of 2 adjacent entries, then an array of size N/4 that contains sums of groups of 4 adjacent entries, etc. When you do a set() on a single element, it updates these group arrays too. When you do a get() on a range, it gets the value by looking at the highest-granularity subarrays it needs to. In the RangeOp class, all of these arrays are actually in a big array of size 2 * nn, where nn is the first power of 2 that is greater than or equal to N, so that is why the code is just doing stuff inside this big array.

More concisely, RangeOp is exactly like a 1-dimensional quad tree. I chose to go with one dimension because that seemed to give a big enough performance gain that implementing a 2D quad tree wasn't worth it. This is why TileClass actually contains an array of RangeOp objects (one per row) that do its counting.

We can come up with a better name for RangeOp, or even a better implementation (e.g. 2D quad-tree). I'm kind of shocked that I didn't document it. I guess it just slipped off my radar as I stopped working on rmgen. Normally I try to document these kinds of datastructures more carefully.

The reason it's called RangeOp, by the way, is because the "operation" we're performing on ranges (sum in this case) could be other operations too. However, there's probably a better name for this kind of datastructure. This is just what I've seen it called before.

[Matei]

BTW, I'm also curious to see if other ways of doing map generation would work better. I went with the TileClass design (where a TileClass is just an arbitrary set of tiles) because it was simple and fairly fast (RangeOp is pretty cheap in both memory and access time). My guess is that a quadtree would perform similarly, but maybe this changes when you implement it in JS.

[historic_bruno]

Tickets relevant to random map system:

#6: Random Map Scripting

#460: Random maps don't work since the new simulation system

The RMS Interface document details an interesting API for RMSs. Maybe worth looking into.

I think there should be a higher-level interface (compared to, for example, how the Cantabrian Highlands and Latium scripts work). It could use the concept of Biomes, to avoid needing to specify every texture or object that might appear in a given map.

Potentially useful functions:

createRiver() - create a river, perhaps from a starting point to an ending point, or following a certain function(s). I think the way water is implemented now, it is all at sea level. Thus the river would have to be level (i.e. not flowing down from a mountain). Maybe in the future, this is something that could change, to allow for waterfalls and more realistic environments.

createMountain() - create a mountain range, maybe following two functions, one for position and one for height.

createPathways() - Useful for guaranteeing there is a way to get from each player to the other. Could be an actual open path on a land map, or water connections on a water map.

createForest() - create biome-specific forest of roughly a given size

createLake() - create biome-specific small body of water, like it could be a swamp in some areas

createBase() - create a player base, which uses starting structures and units for the given civ (can be specified in /civs/*.json)

[historic_bruno]

New ticket for troubleshooting Spidermonkey JIT:

#658: Troubleshoot Spidermonkey JIT

[janwas]

The reason it's called RangeOp, by the way, is because the "operation" we're performing on ranges (sum in this case) could be other operations too. However, there's probably a better name for this kind of datastructure. This is just what I've seen it called before.

Yeah, I've seen this data structure used for "Range Minimum Queries", but since it generalizes to any semigroup, RangeOp seems a decent name.

[historic_bruno]

Here's what I'm toying with now for the skeleton of a random map script:

1. Written in JavaScript (same as simulation, GUI, and AI scripts)

2. Optionally calls LoadLibrary(), which will load scripts for map generator implementations. It loads a whole directory, e.g. "/maps/lib/rmgen/*.js" This lets us switch easily from one implementation to another and test new ideas.

3. Calls InitMapGen() to create the map data structures.

4. Does stuff specific to the random map, like placing mountains, forests, civic centres, etc.

5. Calls ExportMap() to send the results to the engine.

Here's a simple RMS which would generate a blank map with 1 civil centre and 3 female citizens per player. It uses an rmgen-like API:

//////////////////////////////////////////////////////////////////////////////
RMS.LoadLibrary("rmgen");

//////////////////////////////////////////////////////////////////////////////
// initialize map

log("Initializing map...");

InitMapGen();

//////////////////////////////////////////////////////////////////////////////

var numPlayers = getNumPlayers();
var mapSize = getMapSize();


// place players in a circle

var playerX = new Array(numPlayers);
var playerY = new Array(numPlayers);
var playerAngle = new Array(numPlayers);

var startAngle = randFloat() * 2 * PI;
for (var i=0; i < numPlayers; i++)
{
	playerAngle[i] = startAngle + i*2*PI/numPlayers;
	playerX[i] = 0.5 + 0.39*cos(playerAngle[i]);
	playerY[i] = 0.5 + 0.39*sin(playerAngle[i]);
}

for (var i=0; i < numPlayers; i++)
{
	log("Creating base for player " + (i + 1) + "...");

	// get the x and y in tiles
	var fx = fractionToTiles(playerX[i]);
	var fy = fractionToTiles(playerY[i]);
	var ix = round(fx);
	var iy = round(fy);

	// create the TC and citizens
	var civ = getCivCode(i);
	var group = new SimpleGroup(
		[							// elements (type, count, distance)
			new SimpleObject("structures/"+civ+"_civil_centre", 1,1, 0,0),
			new SimpleObject("units/"+civ+"_support_female_citizen", 3,3, 5,5)
		],
		true, null,	ix, iy
	);
	createObjectGroup(group, i+1);
}

//////////////////////////////////////////////////////////////////////////////
// Export map data
RMS.ExportMap(SaveMap());

In order for the RMS to be recognized by the game setup, there is an accompanying raw JSON file:

{
	"settings" : {
		"Name" : "Simple test",
		"Script" : "test.js",
		"Description" : "Simple test of an RMS",
		"BaseTerrain" : "grass1_spring",
		"BaseHeight" : 10,
		"RevealMap": true,
		"GameType": "endless",
		"XXXXXX" : "Optionally define other things here, like we would for a scenario"
	}
}

This is analogous to the ScriptSettings element of a scenario XML file.

[historic_bruno]

Random maps now in SVN trunk

[Pureon]

Awesome work historic_bruno, I'll try it out when I get home!

[fabio]

Random maps now in SVN trunk

Nice to have random map since I already know the current maps. I tried the Latium map and it's working fine. I would have expected a slow map generation but it's as fast as the regular maps.

I noticed some issues, not related to random maps. Warning and missing textures:

WARNING: CTerrainTextureManager: Couldn't find terrain cliff_medit_beach
ERROR: Failed to find file: "art/textures/skins/props/head/pers_fem_a.dds"
ERROR: Failed to find file: "art/textures/skins/props/head/pers_fem_b.dds"

Also I choose the Demo AI with Iberian opponents. For some reasons they created a huge amount of women, but not any soldiers, and sent many of them to my hq.

[feneur]

Just played around a bit with the random maps, the system seems to work great as far as I can see, well done (And I who thought the next release might be a "bug fix and small features release" this is going to be one of the best so far, with Iberians, Random maps, decals, unit silhouettes, and we're still not all that close to release )

When it comes to the actual random map scripts I found a few things which can be improved though:

All maps are square rather than round.

Most maps could probably do with a little more resources.

Cantabrian Highlands:

I didn't find any metal on the map.

There were settlements on the map, they will of course be useful later once territories are implemented, but at the moment... (Should just be to comment out that part of the RMS for now)

Latium:

I might be wrong, but I imagine there aren't all that many palm trees in Italy.

NE Badlands:

No metal here either as far as I could see.

In other words, the RMSs themselves are still in need of fixes, but the system works fine as far as I can tell. It holds a lot of promise, so keep up the good work, and thanks for getting it working (+integrated with the game)

[historic_bruno]

Great suggestions, thanks! That's what it needs to improve

All maps are square rather than round.

OK, I can change the setting to circular easily. The map scripts will need a bit of tweaking.

Most maps could probably do with a little more resources.

Definitely agree with this. And the resource generation is funky, sometimes it's based on map size, others it's the number of players. This should be fixed before they are truly "playable".