4
\$\begingroup\$

So I see one other question of this nature, but it doesn't answer my question, so I figured I'd ask another. I have a simple game, that includes a grid, and the ability to create a maze with walls and portals. Simply enough a portal is a 2-way portal connecting 2 nodes, and a wall makes the node unpassable. I've been doing path-finding with A*, knowing my heuristic wasn't perfect and I'd occasionally get less-than-optimal paths, and I'm OK with this for now, but I've had a few instances where solvable paths, show with no solution.

Here is a quick example of a path my algorithm can't solve:

 A B C D E F G H I 1> - - - - - - - s - 2> - w w w w w w w p 3> - w - - - - - - - 4> - w - - - - - - - 5> p w - - - - - - - 6> w - - - - - - - g s - start w - wall p - portal g - goal

When I'm evaluating potential neighbors in A*, I wrote in that portal nodes should only evaluate their neighbors if they came from a portal, otherwise their only neighbor is where they teleport to. This prevents evaluating node I-3, from I-2 getting there from I-1 (because I-1 isn't I-2's connecting portal), so that's not valid.

However because of the nature of A*, when I get around to evaluating I-2 coming from A-5 it gets thrown out, since that's not the fastest path to I-2. So I never actually get a path to I-3, and never get a path to the goal. I've been thinking through several tweaks that handle this case as well as every other case, but haven't come up with anything. If it helps I can post my code, but it's basic A*, with the assumption of not evaluating nearby nodes unless the parent is a portal.

Any thoughts on how I can tweak my algorithm to handle these cases (and of course not break for every other case)?

Edit: The code isn't too long, so I'll just go ahead and post it in it's entirety:

private static int heuristic(Node current) { return Constants.MapSize.Y - current.simplePos.Y; } internal static List<Node> findBestPath(Node[,] nodes, List<Node> startNodes, List<Node> goalNodes) { List<Node> available = new List<Node>(startNodes); HashSet<Node> visited = new HashSet<Node>(); Dictionary<Node, Node> cameFrom = new Dictionary<Node, Node>(); Dictionary<Node, int> gScore = new Dictionary<Node, int>(); Dictionary<Node, int> fScore = new Dictionary<Node, int>(); foreach(Node n in startNodes) { gScore[n] = 0; fScore[n] = heuristic(n); } while (available.Count != 0) { Node current = available.OrderBy(n => fScore.ContainsKey(n) ? fScore[n] : int.MaxValue).First(); if (goalNodes.Contains(current)) { List<Node> bestPath = new List<Node>(); bestPath.Add(current); while (cameFrom.ContainsKey(current) && !startNodes.Contains(current)) { bestPath.Add(cameFrom[current]); current = cameFrom[current]; } return bestPath; } available.Remove(current); visited.Add(current); Node currentNodeParent = cameFrom.ContainsKey(current) ? cameFrom[current] : null; foreach (Node n in current.getNeighbors(nodes, currentNodeParent)) { if (visited.Contains(n)) { continue; } int possibleScore = gScore[current] + 1; if (!available.Contains(n)) { available.Add(n); } else if (gScore.ContainsKey(n) && possibleScore >= gScore[n]) { continue; } cameFrom[n] = current; gScore[n] = possibleScore; fScore[n] = possibleScore + heuristic(n); } } return null; }

Node.cs:

public List<Node> getNeighbors(Node[,] nodes, Node parent) { List<Node> neighbors = new List<Node>(); if (portal && (parent != null && !parent.portal)) { neighbors.Add(portalsTo); } else { if ((simplePos.Y + 1) <= Constants.MapSize.Y && !nodes[simplePos.X, simplePos.Y + 1].wall) { Node tempNode = nodes[simplePos.X, simplePos.Y + 1]; neighbors.Add(tempNode); } if ((simplePos.Y - 1) >= 0 && !nodes[simplePos.X, simplePos.Y - 1].wall) { Node tempNode = nodes[simplePos.X, simplePos.Y - 1]; neighbors.Add(tempNode); } if ((simplePos.X + 1) <= Constants.MapSize.X && !nodes[simplePos.X + 1, simplePos.Y].wall) { Node tempNode = nodes[simplePos.X + 1, simplePos.Y]; neighbors.Add(tempNode); } if ((simplePos.X - 1) >= 0 && !nodes[simplePos.X - 1, simplePos.Y].wall) { Node tempNode = nodes[simplePos.X - 1, simplePos.Y]; neighbors.Add(tempNode); } } return neighbors; }
\$\endgroup\$

1 Answer 1

Reset to default
4
\$\begingroup\$

The problem here is, that you think of portal as single node - which would be true only if taking the portal would be optional. What you need to do is have (logically, does not have to be physically) two nodes at the portal location. First, the portal start which is only one-way connected to neighbors and to the portals other end node. Second the portal exit which acts as normal node at that location, except it is one way only linked to its neighbours (you can implement the optional portals still by connecting those two nodes of same portal).
tl;dr: instead of one two-way linked node:

n <-> P <-> n

have two one-way linked nodes:

n <- P2e -> n //and P2s at same location not connected to P2e ↑ | c = 0 | n -> P1s <- n //and P1e at same location not connected to P1s

With this setup, the algorithm cannot discard node A5->I2 simply because it never seen the I2 as exit node.

note under line: the available.OrderBy().First() has n(log n) computational (and likely n memory complexity). You can use .Aggregate() for n computational and O(1) memory complexity instead.

\$\endgroup\$
3
  • \$\begingroup\$ That makes sense. Thanks for the answer, I'll give it a go! \$\endgroup\$ Commented Apr 2, 2017 at 14:27
  • \$\begingroup\$ Man that was so easy in the end, I was banging my head with so many bizarre hacks in the algorithm. Thanks again! \$\endgroup\$ Commented Apr 2, 2017 at 14:40
  • \$\begingroup\$ As for the run-time complexity, I was going to swap that out for a priority queue, I just hacked it to make sure everything else would work. \$\endgroup\$ Commented Apr 2, 2017 at 15:03

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.