# A* Pathfinding Wall Detection

The A* algorithm I’m using works great except it ignores walls, leading my AI to walk into stuff. I need to figure out if a node is behind a wall when I’m searching for open nodes, and then add that node to my closed list.

The problem is I can’t think of a great way to do that! I’ve tried raycasting from my node to the prospective node; if the ray hits something that isn’t the prospective node I add the prospective node to my closed list. Unfortunately that completely doesn’t work for some reason (I can supply code if needed, but I don’t think it’s necessary).

I can’t think of a better way to do this. Does anyone have any ideas?

3 Likes

I would suggest using Region3. Roblox actually does something like this internally I believe and they break up the game into chunks of 4x4x4 cubes. Each of these cubes checks if there is a part intersecting it and if it is then the cube (node) is marked as filled. You can reduce the size of these cubes at the cost of performance if you wanted to. I think you can also reduce the search range to within a range of the current position and only path find in the minimal area (distance from start to finish).

He directly said that wasn’t working for him.

1 Like

Can you tell us a little more about what you’re trying to accomplish? If your map is static, it’d be pretty simple to have A* search a static navigation mesh instead of calculating reachable points on the fly.

A picture of your map would help determine if there is an alternative algorithm fit for the complexity.

How do you even make a navigation mesh? I still can’t figure that out.

@Hexcede That wouldn’t work because I’m not putting the nodes inside of parts my AI can’t walk into, they’re just blocked by parts my AI can’t walk into.

@ThanksRoBama That is good for optimization, but I don’t see how that solves my problem.

@pheonixmario This isn’t for one specific map unfortunately. I plan to use this AI as a kind of general purpose thing in many of my games. I would still run into this problem with other algorithms too, wouldn’t I?

Thank you all for your help.

I suppose we should examine your code implementation then. Your original solution actually does sound good on paper, it’s probably just an oversight preventing it from properly functioning.

An important characteristic of any map for pathfinding is not just the presence of nodes at locations, but the connections. Usually nodes in a grid can only be connected to adjacent nodes, and when an obstacle is in the way either a blocked node is placed or there is no node and therefore no connection to that location. Pathfinding ensues by only walking along these approved connections until the goal is reached.

What algorithm are you using to assume that a node on one side of the obstacle is immediately connected to the node on the other side of the wall? Or are you trying to create skip connections by saying that if the connections a-b-c exists then a-c exists?