Sign in to follow this  

path-finding in buliding

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm going to assume by G(n) you mean the heuristic value. You have a couple of choices. You can look at it in 3D and simply get the 3D distance between your current location and the final location. The problem here is that it's a pretty bad heuristic if your goal node is on a different floor.

The second option depends on the layout of your map. If you only have one way to get from one floor to the next (e.g., let's say via stairs), then simply sum up the Euclidean** distances between the starting location and the first set of stairs, all sets of stairs in between, and the final set of stairs plus the goal location. If you want to speed up both this calculation and the convergence of A*, you could store the shortest path distances between all pairs of stairs. That way you get a perfect heuristic from one set of stairs to the next with a simple table lookup. This could be done in a preprocessing step and stored in a file.

If you have multiple sets of stairs then you'd need to try various permutations of stairs between each level. This is where I would definitely suggest the preprocessing step mentioned above.

** If you have basic grid movement then you could also use Manhattan/Octile distance measures, depending on the type of movements you allow.

Share this post


Link to post
Share on other sites
Quote:
Original post by aryx
I'm going to assume by G(n) you mean the heuristic value. You have a couple of choices. You can look at it in 3D and simply get the 3D distance between your current location and the final location. The problem here is that it's a pretty bad heuristic if your goal node is on a different floor.

The second option depends on the layout of your map. If you only have one way to get from one floor to the next (e.g., let's say via stairs), then simply sum up the Euclidean** distances between the starting location and the first set of stairs, all sets of stairs in between, and the final set of stairs plus the goal location. If you want to speed up both this calculation and the convergence of A*, you could store the shortest path distances between all pairs of stairs. That way you get a perfect heuristic from one set of stairs to the next with a simple table lookup. This could be done in a preprocessing step and stored in a file.

If you have multiple sets of stairs then you'd need to try various permutations of stairs between each level. This is where I would definitely suggest the preprocessing step mentioned above.

** If you have basic grid movement then you could also use Manhattan/Octile distance measures, depending on the type of movements you allow.




Thank You.I'll try it

Share this post


Link to post
Share on other sites
Would this special case handling be possible to auto-detect during navmesh generation, to produce some form of hierarchical graph even in a general scenario where e.g. floors may be at different height in different parts of the map (say, there are multiple buildings next to each other or similar)?

Share this post


Link to post
Share on other sites
Try thinking it like this; every cell your actor can reach is one position in the graph. The up stair and the down stair on two separate floors are connected, so you just path across them the same way you go between two adjacent tiles on a given floor. From an elevator, the floor tiles just outside the elevator door on every floor it reaches are accessible (in general).

From that one monstrous graph of 'every standable position in the game', we abstract and heirarchify. We choose to first consider vertical transitions as separating otherwise contiguous areas, like stories of a building. Now, pathing between individual tiles is our L0 pathing. Once you reach an elevator or stair, you can access a separate floor of the same building. We can consider the accessibility graph of the entire building (each node being a fully-accessible region of a floor) as our L1 graph.

So, if we are at a given location on the 6th floor, where there's a stairway that will take us to the 7th floor, this is floor 6, region 1. Past some untraversable rubble, there's an area where there's a stair up to the 7th floor, and an elevator to ground level; that part of floor 6 will be region 2. If we want to get a desk in ground-floor lobby, the pathfinder will first find us a path on the L1 graph; (F6R1, stairs up to F7R1), (F7R1, stairs down to F6R2), (F6R2, elevator), (F1R1, desk). Then the L0 pathfinder will give us a path to walk in each of those areas that will take us to the next one. It doesn't need to provide a path until we get to the floor in question, either, so we don't need to have the map of F1R1 in memory until we reach it.

To a certain degree, aryx mentioned this; the L1 graph (of connectivity between floors and regions) is a representation of paths available on a broad scale, and is meant to assist localized pathing (within a given region).

There's nothing to keep you from either using the L1 graph to extend your world across multiple buildings and the streets between them, or if once your player leaves the building he can just point and click on the next building, you can just keep a list of what floor/region is the "entry level" of each separate building's L1 graph.

Share this post


Link to post
Share on other sites
If the building is a static model then you could have a "pathway geometry" which would show where there is a path. So you would have a surface formed by polygons which you would use to cover all the areas you want to allow "paths" to go to. This is the simplest way to do this that I can think of. You can think of it as a carpet. That "carpet" geometry would not be displayed, it would just be for the path-finding code.

I understand you said you want to use A* but you did not mention whether you have considered the "pathway geometry" choice or not.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

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