path-finding in buliding
Author
I want to use A* algorithm Between the different floors, how can I Calculat The value(G(n)) between two nodes that connected difference floors.How to design f(n)? Sorry for my poor English.Any help would be great.
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.
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.
Author
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
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)?
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.
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.
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.
I understand you said you want to use A* but you did not mention whether you have considered the "pathway geometry" choice or not.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
