If each AI would become its own instance of a routefinder (which means its own marker_t-instance), then the route search could be embedded in the step() procedure of the AI: every step() it performs a limited number of steps in the route finder. The route-finder itself will get a step() method, which do some 100 steps. This step() method can even ensure that it is not called twice within one ai-step.
Thus, other players are not disturbed. The drawback would be, that the found route may be invalid after the search terminates, since someone builds on tiles, that are used by the pathfinder. The ai has to check this and repair the route or restart the search.
Imho, 19 MB should not be too much for modern computers? I imagine the following mechanism
=3= allocate route-finding memory for each player
=2= if that fails, allocate the route-finding memory for two players (human + ai)
=1= if that fails allocate route-finding memory once (for all)
=0= if that fails, simutrans will not be playable (which is the current implementation imho)
Then:
== if each player has its own memory, the step()-able route finding can be used be the ai's
== if each ai has its own route memory, a resource management has to be implemented to enable step-able route finding.
== if only one route-finding memory is allocated, ai cant use step()-able route finding and are restricted to use the conventional code
19 MB isn't much, but with 10 players it becomes 190MB... Your mechanism seems to be a good starting point.
But I think the current AIs have to be redesigned (behaviour tree ;D), in order to support such a 'wegbauer stepping'.
The idea of making the pathfinder step-able is, that the simutrans program gets more control on what the ai's are doing.
My ideas of this pathfinder are
- the pathfinder is built-in in trunk, but customizable by ai (custom weights, multiple start, target, terra-forming)
- but: in each step() it only executes several iterations
- it can check (calling welt->get_steps()) whether it is executed twice within one ai::step()
- if too few instances of these path-finders are available then
- ai's have to apply for resources
- if an ai does not use 'its' pathfinder during one step, the pathfinder is granted to another ai
However, apart from memory concerns (on an iPhone with 128MB main meory 19MB is too much anyway ... ) I think building a way which cannot be finished is not such a great idea and make AI even more complex.