Sign in to follow this  
rpiller

A* considering edges?

Recommended Posts

rpiller    839
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.

Share this post


Link to post
Share on other sites
jefferytitan    2523
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.

Share this post


Link to post
Share on other sites
sjaakiejj    130
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.

Share this post


Link to post
Share on other sites
rpiller    839
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this