Pathing with teleport

Allowing the character to teleport merely changes the underlying structure of the graph (that is, if you can teleport 45 tiles away, then any tile will be connected to all passable tiles within a range of 45. This will change the heuristic function (because you can now jump around using teleports) but otherwise leave the A* algorithm untouched.

Of course, if you have a limit on the number of teleports, things will get harder.

Soo..

for (int y = 0; y < graph.Height; y += 45)    for (int x = 0; x < graph.Width; x += 45)        newGraph[x / 45, y / 45] = graph[x,y];

Something like that?

EDIT:
If I do that I lose waaay too much resolution, though -- I'll do a bit more research.

EDIT#2:
Got what I wanted, just used a rectangle, we'll see how well this works in use, though:

            DateTime pathStart = DateTime.Now;            // Start: 560, 90            //   End:  90, 200            List<PathNode> path = new List<PathNode>();            int goalX = 16;            int goalY = 453;            // Start            path.Add(new PathNode(560, 90, goalX, goalY));            int currentNode = 0;            while (path[currentNode].Score > 10)            {                PathNode bestNode = new PathNode();                for(int y = path[currentNode].Y - 45; y <= path[currentNode].Y + 45; y += 2)                {                    for(int x = path[currentNode].X - 45; x <= path[currentNode].X + 45; x+= 2)                    {                        if (x < map.Width && x > 0 && y < map.Height && y > 0 && tempCollisions[x, y] == 0)                        {                            PathNode node = new PathNode(x, y, goalX, goalY);                                                        if (node.Score < bestNode.Score)                            {                                bestNode = node;                            }                        }                    }                }                //Console.WriteLine("BestNode.Distance = " + bestNode.Score);                currentNode++;                path.Add(bestNode);            }            path.Reverse();            TimeSpan pathLength = DateTime.Now.Subtract(pathStart);            Console.WriteLine("Pathing took... " + pathLength.TotalMilliseconds + "ms");

Takes 0ms.

[Edited by - Insolence on June 7, 2008 6:28:23 PM]

A* works with any network of connected nodes. You just have to tell the function that gets the successors to the current node about the additional edges that a teleport represents -- along with the usual cartesian tile (8 neighbors) or navmesh triangle center-to-center edges of the typical game map). If the teleport connected node is closer to the target then it will be chosen over the adjacents to the current node.

This is assuming your evaluation function is using xyz space to judge distances and the nodes you are teleporting to are also in the same spacial coordinate system.

Well I ran into a few problems with it, for one my old function got stuck in a bunch of places and fell into an infinite loop.

Here's an updated version that doesn't work. Any glaring errors?

        public List<PathNode> GetTeleportPath(int x1, int y1, int x2, int y2)        {            List<PathNode> path = new List<PathNode>();            // Offset to relative coords            x1 -= X;            y1 -= Y;            x2 -= X;            y2 -= Y;            int radius = 30;            var open = new PriorityQueueB<PathNode>();            var nodeGrid = new PathNode[Width, Height];            PathNode firstNode = new PathNode(x1, y1, x2, y2);            firstNode.IsOpen = true;            open.Push(firstNode);            while (open.Count > 0)            {                PathNode node = open.Pop();                // We're there!  Journey complete                if ((node.X == x2 && node.Y == y2) || node.Score < 10)                {                    while (node.Parent != null)                    {                            path.Add(node);                        node = node.Parent;                    }                }                for (int y = -radius; y < radius; y += 5)                {                    for (int x = -radius; x < radius; x += 5)                    {                        if (y * y + x * x < radius * radius)                        {                            int px = node.X + x;                            int py = node.Y + y;                            // Check if we went out of bounds                            if (!(px < Width && px > 0 && py < Height && py > 0))                                continue;                            // Is this tile even walkable?                            if (Collisions[px, py] == 0)                                continue;                            if (nodeGrid[px, py] == null)                            {                                // This pathnode constructor automatically generates a score                                nodeGrid[px, py] = new PathNode(px, py, x2, y2);                                nodeGrid[px, py].Parent = node;                            }                            if (!nodeGrid[px, py].IsOpen)                            {                                nodeGrid[px, py].IsOpen = true;                                open.Push(nodeGrid[px, py]);                            }                        }                    }                }             }            // Offset to world coords            foreach (PathNode node in path)            {                node.X += X;                node.Y += Y;            }            path.Reverse();            return path;        }

Quote:

Original post by Insolence Well I ran into a few problems with it, for one my old function got stuck in a bunch of places and fell into an infinite loop.[...]

Are you sure you understand the basic idea behind A*? That code seems to be missing most of the parts of A*, such as a heuristic. Building the graph while you search it probably isn't a good idea, either - unless the graph changes constantly, you could precompute it from the tile map and then only update it as necessary. The way you build your graph and your graph representation seems odd as well, since generally each node in a graph consists of a list of neighbors rather than a single 'parent' link. Your nested loops increment by 5 instead of 1 so you skip over a lot of tiles, and you don't set the 'score' member anywhere (but you test it inside the if statement that looks for completion).

A* search algorithm

I got it working, thanks though.