Greatly Improve Performance of Precomputation

[FreezePhoenix]

These changes greatly improve the performance of precomputing the map data, as well as laying the groundwork for a vastly improved can_move function.

[FreezePhoenix]

You can run it for yourself on your own local device. The steps to compute the map data are as follows:

cd node
rm data.js
touch data.js
node precompute.js

Note that for development purposes, you may want to add some sorting to the keys, otherwise you will get a different result for data.js every time you run precompute.js:

	let keys = Object.keys(G.maps);
	keys.sort();
	let new_maps = {};
	for (let x of keys) {
		new_maps[x] = G.maps[x];
	}
	G.maps = new_maps;

Inserting this short snippet before the loop in precompute.js ensures the map output is always in the same order.

[Telokis]

Hello, thanks for this PR, can you explain in details what you did, why and the measurements you made to determine the scale of the speed improvement, please?

[FreezePhoenix]

Hello, thanks for this PR, can you explain in details what you did, why and the measurements you made to determine the scale of the speed improvement, please?

Reusing expensive computations (such as a binary search result) and overall improvements to the functions used resulted in a significant increase in performance.

The way I measured performance was simply by running node precompute.js, which prints out the time taken to precompute all sorts of map data.

[FreezePhoenix]

@Telokis On my machine, precomputing all the maps would take 127975ms, or 128 seconds. With the performance improvements, It went down to 72218ms, or 72 seconds.

[FreezePhoenix]

I felt that even though this was a performance improvement in one of the lesser-used parts of the code (map precomputation), since it was an improvement on the can_move function (which is used a LOT), it would be worth sharing because the game uses this a lot on the server and the client.

[Telokis]

Ok, I understand, thank you.
Since this PR changes a lot of things, I'd like to get a comparison of the before/after not in terms of performance but in terms of precision to make sure we have the same results we had before.
Moreover I'm not familiar with the map precomputation itself, I don't know what is being precomputed, yet.

[FreezePhoenix]

@Telokis It produces exactly the same results.

[thmsndk]

I'm a little unsure of the naming of the functions stripped_ is because you've removed things from the original methods? could we perhaps add comments to each function explaining what we are doing differently?

[thmsndk]

I ran a precompute without this PR, figured I'd post the numbers, will post another one for comparison once I check out the, do note I'm getting different timings each time I run it

# node precompute.js                                
Precomputed: abtesting in 1163ms
Precomputed: arena in 2434ms
Precomputed: bank in 145ms
Precomputed: bank_b in 188ms
Precomputed: bank_u in 485ms
Precomputed: cave in 1943ms
Precomputed: cgallery in 14ms
Precomputed: crypt in 2153ms
Precomputed: cyberland in 173ms
Precomputed: d_a1 in 1867ms
Precomputed: d_a2 in 958ms
Precomputed: d_b1 in 927ms
Precomputed: d_e in 23ms
Precomputed: d_g in 289ms
Precomputed: desertland in 6270ms
Precomputed: duelland in 4566ms
Precomputed: dungeon0 in 0ms
Precomputed: goobrawl in 792ms
Precomputed: halloween in 3421ms
Precomputed: hut in 13ms
Precomputed: jail in 182ms
Precomputed: level1 in 432ms
Precomputed: level2 in 110ms
Precomputed: level2e in 250ms
Precomputed: level2n in 496ms
Precomputed: level2s in 425ms
Precomputed: level2w in 228ms
Precomputed: level3 in 674ms
Precomputed: level4 in 559ms
Precomputed: main in 9654ms
Precomputed: mansion in 597ms
Precomputed: mtunnel in 189ms
Precomputed: resort in 70ms
Precomputed: resort_e in 79ms
shellsisland is either un-bounded or the spawn point is too close to an edge [server_bfs2]
shellsisland is either un-bounded or the spawn point is too close to an edge
Precomputed: shellsisland in 7731ms
Precomputed: ship0 in 192ms
Precomputed: spookytown in 3641ms
Precomputed: tavern in 126ms
Precomputed: test in 0ms
Precomputed: tomb in 853ms
Precomputed: tunnel in 1118ms
Precomputed: winter_cave in 996ms
Precomputed: winter_cove in 1968ms
Precomputed: winter_inn in 84ms
Precomputed: winter_inn_rooms in 57ms
Precomputed: winter_instance in 224ms
Precomputed: winterland in 7747ms
Precomputed: woffice in 104ms
Done: 66615ms