# A* considering edges?

This topic is 2452 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 on other sites
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 on other sites
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 on other sites
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.

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5

• 11
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633756
• Total Posts
3013707
×