Topic: [AI] custom ai path finding

[Dwachs]

Maybe then a real AI only routefinder is needed with its own tile list to avoid freezing the user interaction.

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.

[Dwachs]

Does the ANode-array in route.h takes 19MB (max_route_steps = 1,000,000), or I am failed with simple arithmetic? Then much memory would be needed, if every AI gets its own routefinder. But it's a very elegant idea. Maybe we should think of one array for the player and one for all AIs?

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

[gerw]

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 ), in order to support such a 'wegbauer stepping'.

[Dwachs]

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

[prissi]

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.