2
\$\begingroup\$

I try to create a "AI" that can move independently on a map structure where the individual maps are only connected by one directional teleport squares (links).
There are some map areas you can only traverse if you fulfill some requirements.
(for example you could be too heavy to swim.)
Movement is limited to 4 directions.

So far I use A* to navigate on a single map.
For the shortest path across multiple maps I came up with a pre-generated graph.
I use the links as nodes and search with Dijkstra because I wasn't able to come up with a working heuristic for that (no spatial arrangement of the links).
I generate the graph by calculating the cost for every link target square to all other links on that map. (tons of A* searches per map, takes 8-10 minutes to complete).

Then, for an actual search, I temporarily inject the start and end-point as links into the multi-map-graph (and do the cost calcing using A* without persistently saving it) so I can find the fastest way to the goal.
I get a list of goals, one goal per map out of that and just need to do an A* search for each goal on the corresponding map.

The tricky part in my approach is that the costly pre-calculated data isn't able to reflect the dynamic conditions for example swimming. (sometimes there is a completely different route necessary.)

Now on to my question(s).
Is there a known solution to this combination of problems that I'm just unable to find?
Has anyone already faced something similar?

There are some conditions that I want to meet. I'm already almost at the memory(ram) limit (that I'm willing to sacrifice) and I want to keep the disk IO as small as possible (multiple ai would be kill).
I thought about just pre-calculating path for every possible condition and at the moment that could actually work but I'm 99% sure that this wouldn't work in the future (because the size grows exponentially).

\$\endgroup\$
8
  • \$\begingroup\$ What's the density of your grid. Why not do astar at runtime \$\endgroup\$ Commented Jan 19, 2016 at 0:41
  • 1
    \$\begingroup\$ I do A* at Runtime. but only per map. As I said I don't know a heuristic to use across multiple maps. there are roughly 1000 maps (will be at least up to 5k in the future), 200x200 each. I would need to search with Dijkstra. that takes up 20 seconds for a single path. that's not acceptable. ram usage would explode too."I get a list of one goal per map out of that and just need to do an A* search and walk that for every element." \$\endgroup\$ Commented Jan 19, 2016 at 0:47
  • \$\begingroup\$ Use two tier HPAstar its a hierarchical approach. It's designed for your situation. \$\endgroup\$ Commented Jan 19, 2016 at 3:19
  • \$\begingroup\$ It seems like you don't understand my explanations but I don't know how to describe it better. If it would be so easy I had no reason to ask. If I calculate a path respecting the "dynamic" parts I'm guaranteed to get a valid path to the end. There is no problem with early path invalidation (the problem that HPA* adresses) \$\endgroup\$ Commented Jan 19, 2016 at 4:35
  • 1
    \$\begingroup\$ I will try to draw a sketch tomorrow to better show what I mean. \$\endgroup\$ Commented Jan 19, 2016 at 4:54

2 Answers 2

Reset to default
0
\$\begingroup\$

For dynamic paths, the D* family of algorithms is a good place to start. It is very similar to A*, but whereas A* must be completely recalculated whenever the shortest path changes, D* can incrementally recalculate only those parts that are affected by the path change. It can still be very expensive, e.g. if the path becomes blocked requiring a very long detour, but for minor path changes it is efficient.

But I've found that for the best performance, it is better to take as much advantage of your specific situation and make some non-optimal assumptions. HPA* is a great example; it is non-optimal but is responsive and very fast. Try to do the same, like producing a graph made up of all the teleport ends, and assuming all the teleports within the same map are accessible, falling back to D* if they are not.

\$\endgroup\$
1
  • \$\begingroup\$ I found out about D* myself just days ago but in the end, my problem was the language. Python. The time needed to traverse a node is just too big regardless of the algo. I learned quite a lot about graphs and their properties too and in the end, I think that the only real solution is a simplified/optimized graph (e.g. a QuadTree) but D* is the best tip so far on top of a full graph. I heard about hpa* a lot too but it just doesn't fit my problem because in my case the result would be quiet aweful without any kind of heuristic. \$\endgroup\$ Commented Nov 15, 2016 at 15:53
0
\$\begingroup\$

If you have a list of all available teleports per map containing information about their position and what map they link to, you could find out in a first step which teleport will bring you the closest to your target and then do a local A*-search to that chosen teleport.

\$\endgroup\$
1
  • \$\begingroup\$ I have over 1000 maps and for some paths I need to travel through over 100 teleports. furthermore, how do I know if a teleport is close to my goal position if it doesn't bring me right to the correct map? \$\endgroup\$ Commented Jan 19, 2016 at 12:20

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.