Slow pathfinding for Silver Mage/Teleport on huge maps

[phoe]

Slow pathfinding for Silver Mage/Teleport on huge maps

[gfgtdf]

The issue talks a lot about a* which is an algorithm to find the shortest paths between two points, but the process of calculating the reach map should be the main limiting factor since it calculates the distance to all points.

Maybe it we can optimize a lot already with caching that one better

[CelticMinstrel]

it does sound like there's not much room for further optimisation.

It probably couldn't hurt to do some benchmarking comparing Wesnoth's A* with some other versions of A*, but I'm at least not aware of anything that could be done to optimize it further. That doesn't mean there is nothing, however.

Also, what I said earlier isn't quite accurate. The size of the map will certainly have an effect on pathfinding. I think expanding a map by one row would add a number of edges equivalent to about twice the width of the map, and expanding a map by one column would add a number of edges equivalent to about twice the height of the map. So maybe that does outweigh teleport for larger maps with fewer villages. I don't really know what's an average number of villages on a 100x100 map, so I can't say for sure, but generally speaking, if you have 60 villages, adding one more village is equivalent to an addition 60 edges. Adding another is equivalent to 61 more edges, and so on. So it's quite possible that expanding the map actually adds more edges than adding a teleport point, in some cases.

But looking at the algorithm more closely, the number of edges is not the sole factor. There's also a heuristic used to guess which is the best direction to go when all else is equal. Since Wesnoth's A* is optimized for a hex map, the heuristic is presumably a hex-based distance metric… which becomes a terrible heuristic in the presence of a large enough number of teleport points. In technical terms, I think the heuristic becomes inconsistent in this case. I'm not entirely sure what effect this has on the efficiency of the algorithm though.

[Wedge009]

Two machines: Zen2-based Threadripper running Linux and Ivy Bridge-E Core i7 running Windows 7. I'm assuming this is all single-threaded processing so number of cores should be irrelevant - I observed CPU usage saturation but only for a single core.

Both using 1.18.2 release. I started a local 2p MP game with a generated field of maximum size (100x100) and maximum village density (50 per 1000, 500 in total). I debug-create about 20 or so Silver Mages and use them to capture villages and then on the subsequent turns moved them off so the movement mapping would show. The Ivy Bridge system felt subjectively less responsive and more 'jittery' but certainly nowhere near the 10 second response time mentioned. So I created another 20 Silver Mages and repeated the process to expand the movement mapping yet again. Still not that bad, not even a second to respond.

So I wonder if there's something else going on for you. Maybe provide a saved game where you're experiencing the 10 second movement?

[phoe]

Here's a probably-overblown example (generated via current Wesnoth maximum, 200x200 + maximum villages) that I've managed to play through in order to demonstrate the problem. Select one of the Silver Mages at the frontline, try to move.

[CelticMinstrel]

A* is an algorithm on graphs, not maps, so in effect it simply treats villages as adjacent when considering teleport. That said, Wesnoth's version of A* is simplified for the hex map, using an extra list of adjacencies for teleport. This is entirely off the top of my head since I don't have the code in front of me at the moment, but I think the size of the map shouldn't be relevant to performance, only the number of teleport points. This is supported by Wikipedia, which says the worst-case performance is O(ElogV), given that teleport points (at least for the silver mage) form a complete subgraph, so adding one more point means almost doubling the number of edges.

So I don't think ignoring villages the mage can just walk to would help performance that much, and I bet it would also slightly reduce their potential range in some configurations. Use of those villages could very well be the only way to reach a certain hex (by saving the movement points that would've been used when teleporting from a further village).

[phoe]

I see - so there's no good way to separate non-teleports from teleports when doing A*. If we were able to do this, then we could separately compute the non-teleport case (just walking around) and the teleport case (to-village and from-village, keeping track of the extra movement point spent on teleporting); finding the pair of villages closest to source and destination should be much, much cheaper than running a full A*, and in case of no match on the fast path we could - in theory - fall back to the full search.

[CelticMinstrel]

Don't forget that a unit could also teleport twice in a single move. Obviously that's not going to happen with a silver mage just teleporting through villages (because for every path with two teleports, there's a shorter route to the same hex with only one), but if a unit has two different teleport abilities, or if there are general-use tunnels on the map that can be used by all units, then it could easily happen.

[Wedge009]

...can take over 10 seconds on my machine.

Out of curiosity, what is the CPU in your machine? Not suggesting that 'just upgrade' should be a solution for you, but it does sound like there's not much room for further optimisation.

[phoe]

/proc/cpuinfo gives me Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz.

[Wedge009]

Fairly old, but by no means a low-powered CPU. I still run i7-4930K (Ivy Bridge rather than Haswell) machines, when I get home I'll see how it compares with my primary machine.

[CelticMinstrel]

So if I read correctly, that's a 100x100 map with around 40 teleport points (as uncaptured villages can't be teleported through). I wonder how much it would change if all 500 or so villages were owned?

[Wedge009]

I don't have the patience to try that right now... I was under the assumption that the algorithm was of polynomial complexity so even a small increase in the number of entry points could be noticeably slower. I didn't perceive much difference so I left it at 40 for the time being.

[CelticMinstrel]

It's certainly understandable that you wouldn't want to spawn 500 silver mages. For that sort of test, I would probably use the Lua console to instantaneously give all villages to the current side. I'm not sure the exact code that would be needed for that off the top of my head though.

The algorithm is not of polynomial complexity, but I'm pretty sure O(ElogV) is better than O(E×V), right?

[phoe]

Mapa użytkownika Tura 37.gz

[Wedge009]

Okay, that's really stretching the limits of the engine, it was a crawl on my Threadripper system. Not even sure how you endured to play even that far. I saw 1519 villages owned before I gave up, let alone total number of villages.

Not sure what we can do, with such a large play area. Personally I don't think it's a reasonable size but clearly you have managed to play it!

[Zireael07]

Might be worth reducing the maximum map size allowed?

Or investigating things like hierarchical A* or jump point A*

[phoe]

Okay, that's really stretching the limits of the engine, it was a crawl on my Threadripper system. Not even sure how you endured to play even that far. I saw 1519 villages owned before I gave up, let alone total number of villages.

Not sure what we can do, with such a large play area. Personally I don't think it's a reasonable size but clearly you have managed to play it!

@Wedge009 It's a maximum currently offered by Wesnoth map editor, so I gave it a go just out of curiosity. I don't think it's reasonable either, but all progress depends on the unreasonable man. /s

I noticed that it's manageable with non-teleporting units, as in, I can order a move to the other side of the map without a noticeable delay - so it doesn't seem that the 200x200 map size on its own is a problem. Silver Mages are a pain to move around though, hence my suspicion that something's problematic with teleports only.

[Wedge009]

It's a good 'stress test' scenario, certainly.

[CelticMinstrel]

Might be worth reducing the maximum map size allowed?

There actually is no maximum map size in the engine. The editor doesn't give an option to create really, really large maps, but it will load and edit them without issue as far as I know (in the past it got slow really fast on large maps, but I bet that's not the case since the rendering reworks).

the process of calculating the reach map

What algorithm is this process using? Is it also using A*, or is it using something else, like Djikstra's algorithm for example?

[cooljeanius]

Related example from an add-on: nemaara/Genesis#5