🔒 Locked

A* considering edges?

Started by rpiller Apr 1, 2012 at 7:24 PM 2 replies 1.9k views

Original Post

Apr 1, 2012 at 7:24 PM

I've done A* before in the past but it's always been a tile is walkable or not and that's it. If I want to consider if one can pass through a tile, how would I incorporate that? Basically I want my walls to be skinny and on the edges of my grid, which means if there is a wall on an edge the player can still walk on the tile, but not through that tile to the other on the other side of the wall.

Sort of like the original Sims and how they did walls.

Is there a term for this, and are there any articles that talk about this, or better yet a library in C++ that handles this already?

Also, are there any well created A* C++ libraries out there designed around a 2D grid? I found one but not sure how good it is yet and just curious if there are any that have stood the test of time.

jefferytitan

Apr 1, 2012 at 8:17 PM

If I recall correctly, the basic implementation of A* does take edge weights into account. However in tile-based terrains many people have simplified the algorithm to treat a node=an edge. If memory serves, A* even correctly handles one-way edges, e.g. dropping off a ledge that you can't get back onto.

sjaakiejj

Apr 1, 2012 at 9:23 PM

You'd have to define the relationship between your grid nodes differently. A grid, to A*, is just a graph, and any node that is connected to another node is automatically possible to navigate. You'd either have to remove those connections (for instance, at the point on which you get the adjacency nodes, check if there's a wall obstructing the path from the current node to the one we're looking at), or change your approach from a grid to something like waypoints or a navigation mesh.

I think the Sims uses NavMeshes, but I'm not a 100% sure.

rpiller

Apr 1, 2012 at 9:34 PM

I'd be shocked if the very first Sims was a navmesh being 2D, it's pretty old, so much is dynamic since the user gets to build everything, and it flat out shows you a grid when building, which I'm guessing is the same grid they use for the pathfinding graph.

I can't imagine waypoints are used since those seem to work best when defined at design time not run-time.

So do you think that as we are looking at adjacent nodes we can lookup if there is a wall between them and if so, consider it unpassable? Maybe in the node structure I can have 4 flags for the edges where 0 = no wall & 1 = wall. Then when looking at adjacent nodes (let's say the node to the right of current) I first check if the node itself is open, and if it is, I then look at that nodes left edge value and if it's 1 (wall) consider it not open also?

I guess the current nodes "right edge" would share the wall so it would be 1 also. So really before checking adjacent nodes I first look at the edge of the current node for that adjacent node and if there is a wall skip that node? I just don't know if that would flow correctly through the entire algorithm. At first glance I would think it would.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.