Hi, My problem sounds fairly easy. I have a game with a huge map. All I need to do is calculate the distance between two points. Easy enough, isn't it? A week ago, however, I've began working on portals. A portal is some kind of teleport that zaps units from one location to another location in a split nanosecond. This makes travel times a lot shorter since the distance between two players will be a lot less. I've tried to implement this system in A*. A very simple example of what I need: - Player A has a village at (10,0) - Player B has a village at (90,0) - There is a portal that links (0,0 to 80,0) - There is a portal that links (50,0 to 654278,0) When I calculate the distance between A and B, I should find 20: - 10 to reach the first teleport - 10 to reach B from the first teleport Sounds easy enough, but I've had a hard time implementing this. Since you can basically go from any point to another point, every point is neighbor with every other point. (In case there are no portals, units should march from A to B). This is where I am now: http://daedeloth.no-ip.org/Distance.phps (There is some debugging in there, but the script is essentially the model A* code). However, since every point is neighbor with every other point, all points are connected to the start point. The way I've programmed it (and Wikipedia showed me how to do it), that means that the "came_from" value of each node is start. Since every node is only "initialized" once, "came_from" is "start" for every single node. Same goes for total traveled distance ($g). That makes it impossible to display the route or calculate the distance. When running the code, it does find the route without much trouble. It just can't store it anywhere, it's lost due to the above problem. Any ideas how I can fix this? Thanks, Thijs.

Quote:However, since every point is neighbor with every other point, all points are connected to the start point.

No, every point is not a neighbor to every other point. Nodes that contain portals are connected to their immediate neighbors and what their portal is connected to. From what you have described this is not every point and not every other point. The only thing you need to do differently in H is determine distance from each portal as well as straight line distance and use the shortest.

Hi,

Mind that portals are not the only way to travel. You can very well travel part of the distance by foot, then use a portal, travel another while by foot and take another portal.

Also mind that portals work in two ways.

I have made a little test script here:
http://daedeloth.no-ip.org/dolumar/test/distance

As you can see on the rounds, the proper route is selected eventually:
(-67,69) -> (-58,68) -> (77,-129) -> (68,-127)

However, since in round 1 all neighbours are loaded already (including the end point, by foot it's 237.99 units) the end point gets a "came_from" value to the start location.

Since only new nodes are inserted, this never changes. So there is no way to trace back the route or to calculate the actual distance: everything is set in the first round.

The route-searching seems to work like a charm, but I can't trace it back nor calculate the distance because the "came_from" values are completely wrong, right from the start.

Thanks for the help,
Thijs.

Ps.: I'm not working on a tile basis. One node is not one "distance unit". I just make 2 nodes for every portal.

Distances over 5000 are not uncommon.

Since the map is rather huge, checking every single tile would be a huge task. This is a browser based game, I can't have the server spend seconds on one single distance calculation.

I'm not really sure what the problem is. When you are pushing neighbors onto the open list, there are several neighbors of a portal node: the actual geographic neighbors and the portal exit point node. the cost to go from the portal node to either the exit or a geographic neighbor should be the same (i.e. the G cost of all neighbors, including the exit would be the same or relatively the same). The magic happens when H is significantly lower for the portal exit. On your next iteration you're going to pop the portal exit from the open list because it's F score (G+H) is dramatically lower. So then your search just continues normally and you get portal traversal for free. This is an easy problem and your cameFrom should always be correct unless you just have a bug in your basic A* implementation.

The next step comes in path-following. When an entity hits a node where the next is a portal exit and the current is a portal, your pathfollowing logic does whatever is necessary to make that deal happen correctly (play teleport anims and effects and whatnot). But this is something in the unit state machine and has nothing to do with the actual pathfollowing.

Perhaps you should post your A* implementation since if cameFrom is bugged and if portal traversals aren't working, there is probably something wrong in the fundamentals.

If you have craptons of nodes, you should look at Hierarchical A*. Pathfinding is always a super expensive problem. Also consider time-slicing your pathfinding jobs: make them non-blocking calls. i.e. request a pathfind and then wait for a callback. that way you can tune the amount of time your A* spends per frame and get better overall responsiveness.

-me

I'm with Paladine on this. It sounds like perhaps you've fallen into the mental trap of thinking of A* as "something that works on grids" or that it somehow has something to do with space. Apart from the heuristic, "h," it doesn't. It's a graph search algorithm. It can search on any graph, including ones that cannot be realized in Euclidean space (without overlapping edges). Here the graph is obvious: You start with the graph corresponding to your grid, and then add some edges corresponding to your teleporters, and then search on that graph.

The only issue is choosing an appropriate heuristic. This is a lower bound on the cost-to-go, nothing more.

On a grid, we usually use what I'll call the "free distance" as this bound -- by which I mean the distance you'd travel if there were no obstacles; this is usually the Manhattan distance. This is indeed a lower bound because obstacles can only make your path longer.

Here we cannot use this heuristic because there may be paths which are shorter than this, thanks to teleporters. But this is the only problem: coming up with a good heuristic. And this is just an issue of efficiency, as you can always choose h=0 and be guaranteed the shortest path (in this case A* reduces to Dijkstra's algorithm). So for now use h=0, and in this thread we can try to come up with a better one. Fair 'nuff?

Quote:Original post by Emergent
Here we cannot use this heuristic because there may be paths which are shorter than this, thanks to teleporters. But this is the only problem: coming up with a good heuristic. And this is just an issue of efficiency, as you can always choose h=0 and be guaranteed the shortest path (in this case A* reduces to Dijkstra's algorithm). So for now use h=0, and in this thread we can try to come up with a better one. Fair 'nuff?

No. You can still definitely use Manhattan Distance or just straight up distance for H. Adding teleporters doesn't require a change to H, only a change to G for teleporter exits and then only if you arrive at them from a teleporter entrance (their G then being simply G_CameFrom + G_TeleportCost). The latter being tweaked to be somewhere around the cost of G_MoveToAdjacentNeighbor + some fudge factor to account for the time needed to play teleporter effects.

Basically the only change you need to get A* happy with teleporters should be a single line code change:



-me

Quote:Original post by Palidine
No. You can still definitely use Manhattan Distance or just straight up distance for H. Adding teleporters doesn't require a change to H

...But once you add a teleporter, h ceases to be an admissible heuristic because the cost-to-go might NOT be that of the obstacle-free overland path; it might instead be the length of a path which passes through a teleporter.

Using Manhattan distance for h would not completely break A*; the algorithm would still return feasible paths. But those paths would not be optimal.

Ah, yes, you are totally right. Yes, I see the problem. Sorry =)

h=0 would be a viable short-term solution in terms of "it'll work, it'll just be slow"

-me

Hi,

I am, indeed, starting to think there is a bug in my implementation.

At the moment I add my neighbor nodes to the "open" list, I have to set the came_from value for this node, right? But when there are multiple ways to reach this node, you only know the first way.

The code can be found here:
http://daedeloth.no-ip.org/Distance.phps

This is basically the whole implementation as provided in the pseudo code.

If anyone can spot an error, please share :) I've been looking for the issue here for a few days now.

I still can't understand how I can change the "came_from" parameter of a node that already is in the open array...