Question Pathfinding on Grid with Wall

Hello everyone !

I'm trying to make a Pathfinding algorithm for a Grid with walls.
Here is an image to explain:



I tried to look at a lot of information about algorithms in Grid, but these don't use walls, but put tiles entierly unwalkable.

I would like to find an algorithm that takes into account the fact that (for example) if the tile is not accessible from the right, it can be from other directions.


Does anyone have a link, a doc, or an example to put me on the right way?

Thanks for helping me !

 

This makes me think of Micro-mouse stuff. This video, while not necessarily about programming, does describe the high-level techniques used to navigate these kinds of mazes:

They could definitely be transferred into programming ideas.

 

Generate graph with each cell being node and each wall preventing creating edge between two nodes. Then just A* it as usual.

 

I had a similar problem, but with a hex map, and each hexside may have a river, impassible or a road which all impact on movement of units across the map. I used an Int, which contains 32 bits to store 6 sets of 6 hexside true/false for roads, rivers, impassible sides, borders etc. I had a large map so wanted to save space.

If your map is small you could just use 4 bools for each cell like this:

Code (CSharp):

1. public class SquareTile    // Class for a Square tile on the Map
2. {
3.     public Bool CanGoNorth;
4.     public Bool CanGoSouth;
5.     public Bool CanGoEast;
6.     public Bool CanGoWest;
7.  
8. }

You could hold your map in a 2D array Map[x,y]

To "draw walls" in your maze you would set or unset these bools for each map x,y location, and test for legal moves between squares with a function:

if (Map[x,y].CanGoNorth) {// you can move north} else {// You can't move north}

if trying to move north from x,y.

Hope this makes sense, let me know of you want more details to this approach.

 

... or just encode stuff in single byte or whatever with bit masks, so CPU won't choke on cache.

 

very nice vid @spiney199 , thanks!
and now the micro-mouse jingle is stuck in my head.. yay.. thanks..

But upon finding one of my old pathfinding snippets:

Code (CSharp):

1. public static List<Tile> FindAnyPath(Tile startNode, Tile targetNode)
2.     {
3.         List<Tile> toSearch = new List<Tile>() { startNode };
4.         List<Tile> processed = new List<Tile>();
5.  
6.         while (toSearch.Count > 0)
7.         {
8.             Tile current = toSearch[0];
9.             foreach (Tile t in toSearch)
10.                 if (t.F < current.F || t.F == current.F && t.H < current.H) current = t;
11.  
12.             processed.Add(current);
13.             toSearch.Remove(current);
14.  
15.             if (current == targetNode)
16.             {
17.                 Tile currentPathTile = targetNode;
18.                 List<Tile> path = new List<Tile>();
19.                
20.                 while (currentPathTile != startNode)
21.                 {
22.                     path.Add(currentPathTile);
23.                     currentPathTile = currentPathTile.cameFrom;
24.                 }
25.                 path.Reverse();
26.                 return path;
27.             }
28.  
29.             foreach (Tile adjacent in current.adjacentTiles)
30.             {
31.                 if (!processed.Contains(adjacent))
32.                 {
33.                     bool inSearch = toSearch.Contains(adjacent);
34.                     float adjacentCost = current.G + current.GetDistance(adjacent);
35.  
36.                     if (!inSearch || adjacentCost < adjacent.G)
37.                     {
38.                         adjacent.G = (int)adjacentCost;
39.                         adjacent.cameFrom = current;
40.  
41.                         if (!inSearch)
42.                         {
43.                             adjacent.H = (int)adjacent.GetDistance(targetNode);
44.                             toSearch.Add(adjacent);
45.                         }
46.                     }
47.                 }
48.             }
49.         }
50.         return null;
51.     }

The only thing I can think, is while in the "foreach adjacent" part, that you would also have to calculate in the variables of "hasWall" and of course each direction, of each tile. Meaning both the one you're on, and the one you plan to search next both need to have the same wall in their variables(at different directions). But even to calc that, would require giving it a higher G cost, which in turn would give false results of the tile "before" wall.. hmmm...

This definitely has me scratching my head, but I am curious. I will continue to explore

 

Ahh, just thought of it, like I show here(in above code):

Code (CSharp):

1. foreach (Tile adjacent in current.adjacentTiles)

I have each tile(before search) find it's adjacent tiles(and add to list). So with setting those adjacent variables, simply that tile would check the one next to it, see it has wall(between them), and not include it in it's adjacent List!

Yup, simple fix

 

A* with a smaller grid would be a possibility