Path calculation with non grid nodes
Blitz3D Forums/Blitz3D Programming/Path calculation with non grid nodes
| ||
| Hi, :) I'm currently coding the pathfinding routines for a video game. I have already coded a routine to create nodes, a routine to create links between the nodes, a routine to calculate the shortest path depending on the links between the nodes and AStar concepts, a routine to make a npc follow the path. This works well, but the nodes are positioned on a grid, so it is easy to find the start node and the end node with a simple distance check between the npc and the nodes of the room or the player and the nodes of the room. Like this :  I want to be able to use nodes positionned around the obstacles (furnitures or buildings) like this :  As you can see there are nodes around each obstacle, and links have been already precalculated with linepick. But with these nodes i can't simply use a distance check to know what is the start node and the end node because the nearest node may be behind an obstacle... I know i can use linepick to check if the nearest node is behind an obstacle or not,but i don't want to kill my fps if several npcs want to create a path at the same time. Do you know others ways to achieve this ? Your thoughts ? Thanks, Last edited 2012 |
| ||
| Is EntityInView slow? I don't know much about it. |
| ||
| Hi Rem, if I'm not mistaken A* will still work in this case. It can be applied to any structure of nodes, even if they're not on a grid. Distant nodes (in your case, the ones behind the obstacles) will have a bigger walk distance and thus a bigger cost to travel. A* will first process the closest ones (the ones that don't reach the goal) until it processes the costlier ones that circumvent the obstacles and actually reach the goal. For further info check this link: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#polygonal-maps |
| ||
| Stayne>> Good idea, i will do some tests. Thanks. Kryzon>>Thanks, but i know how to use Astar. The question was how to find without too many calculations, what is the nearest node from a character or what is the nearest node from the Player, knowing that with nodes positionned without a grid, there can be an obstacle between two nodes, so the distance check is not reliable. So i guess linepick or entityvisible is the best way to do it ? |
| ||
| I do remember EntityVisible being VERY slow. |
| ||
| The fastest way would be to create a cell diagram covering your space (AKA Voronoi map), which would allow you to quickly attach whole areas of space to nodes. You could use a pixel-based version, finding the nearest position on a very fine grid to where the character is and testing the "colour" of the matching pixel; or you could create convex-hull descriptions of each cell and test if a point falls "within" any given hull, starting with those belonging to nodes nearest to it (but for this to be any good you'd need a way to quickly pre-sort small groups of nodes, perhaps using quadtrees). On the other hand... remember that premature optimisation is the root of all evil. Until you've seen that LinePick isn't fast enough for your needs, assume that it is. When it gets slow, swap from B3D collisions to ColDet and keep using LinePicks until again you need change strategy later - but remember, how you do it is just an optimisation and implementation detail - get your whole system working first. |
| ||
| Thanks, but i know how to use Astar. I know you know, you mentioned it in your post! :) I like to give context because some people that read these threads might not be initated. I did misunderstand the question... Since we're talking about a 2D top-view, you can use a 2D euclidean distance check on the X ~ Z plane. Thing is, you're comparing distances with themselves, so you can optimize your distance function by removing the Sqr(). You won't be able to consider the result as an actual distance value, but you will be able to compare results and tell which node is closer. Function QuickDistance#( X1#, Y1#, X2#, Y2# ) Return Abs( (X1 - X2)*(X1 - X2) + (Y1 - Y2)*(Y1 - Y2) ) EndFunction ;Run the above for every node against the player, and pick the one with the smallest result. ;This will be your closest node.This is something GfK always recommended around here. Without the Sqr() the above is quite fast. Last edited 2012 |
| ||
| Stayne>>I think EntityVisible is not appropriate in this situation because i need to check if a path with a radius is possible between a point to a node (the radius is the width of the character). Yasha>>I hear your advice, but i guess that if my program has to use 10 times linepick for each character during a loop, this will surely kill my fps. But a try is better than a guess, so i will try :) Kryzon>>Ok now i know that you know that i know. :) |
| ||
| I have another question about collisions detection related to this topic : Let's say i use a collider sphere with a radius of 0.5 (the max width of the characters), and all furnitures are collider meshes. I use collisions detection instead of using linepick, i calculate the VLength# between the character X,Z coordinates and the node X,Z coordinates using a 2D distance calculation. I put the collider sphere at the character position, then i use PointEntity or RotateEntity to make the collider sphere faces the node, then i use : MoveEntity(Colliderphere,0,0,VLenght#) In theory if i use : NCCS% = CountCollisions(SphereCollider) If(NCCS% > 0) OCEntity% = CollisionEntity(SphereCollider,1) OCName$ = EntityName(OCEntity%) CX# = CollisionX#(SphereCollider,1) CY# = CollisionY#(SphereCollider,1) CZ# = CollisionZ#(SphereCollider,1) CNX# = CollisionNX#(SphereCollider,1) CNY# = CollisionNY#(SphereCollider,1) CNZ# = CollisionNZ#(SphereCollider,1) EndIf this will check the collisions which have happenned between the collider sphere and the collider meshes before reaching the node. However how am i supposed to use the index of collisions ? What does this index mean ? My guess is that the first index (1) represents the first collision and thus i should use this first index (1) in order to retrieve the parameters of the first collision ? Yes ? No ? Why ? Thanks, Last edited 2012 |
| ||
| Pretty much. Internally a list of collisions is built for each collider; CountCollisions give you the length of the list and that index lets you get at specific elements of it. This is essentially useful only if the entity collided with more than one thing. It's a convoluted solution you're going for there though. I would repeat the suggestion that you look at ColDet. Not only is it blazingly fast (dozens of times faster than native collisions), it also supports linepick-with-radius (not called that, but eh) so it basically has the function you want built-in. EDIT: Checking the docs and... OK, I honestly just forgot B3D also supports pick-with-radius as part of the standard LinePick command. Well, ColDet should hopefully be faster anyway. Last edited 2012 |
| ||
| Ok i'm going to do some tests with Blitz3d Linepick, Blitz3d collisions, and Codlet. I will post the results. Thanks, |
| ||
| Not sure if this was suggested before - or applies to you, but a good way to deal with costly routines during your main loop, is to NOT try to solve everything in the same frame. For example if you need 25 linepicks to reach your solution, Split your routine so (for example) it does do more than 4 linepicks per main loop - so it doesnt kill your frame rate. As a result your Npcs will need more time to 'think' about the solution, but thats only realistic, and still only a matter of milliseconds... D. |
| ||
| ^^ Also AI generally doesn't need to be updated every frame for things like path finding/movement - infact most AI stuff won't need to be done more than at about 10fps which give a good compromise between them reacting to stuff quickly enough but also giving them some "thinking" time. The only potential issue then is uneven frametimes creating "lumpy" rendering performance makign the game feel unsmooth but thats something thats possible to work around i.e. like you said distributing the payload over multiple frames when needed. |
| ||
| And you can actually use it to your advantage. Put low-priority npcs in a queue, and play an animation where they scratch their beard, look around if lost, etc whilst their routines are waiting to be served ;) it's fun stuff to toy around with.. |
| ||
| And if the environments of your levels are non-dynamic (they aren't destructable or change while playing), you can pre-calculate the visibility all nodes have of eachother, and which zones give access to which nodes. Having 'n' nodes, node visibility would be a bit array (only 'true' or 'false' values) of: NodeVisibility(n, n). -> which 'n' nodes are visible to a certain 'n' node (used for pathfinding). Having 'z' zones, each zone's visibility of nodes would be a bit array of: ZoneVisibility(z, n). -> which 'n' nodes are visible for zone 'z' (used to dock the player to the closest visible node and initiate pathfinding). Zones are delimited by obstacles and the shape of the level - depending on which zone the player is at, he won't be able to see certain nodes (if I'm not mistaken this is what RemCoder's been concerned about). Zones don't overlap with eachother. Somewhat similar to NavMeshes. Pack all this data in those look-up tables (which are nothing more than arrays smartly indexed for loop efficiency) and you got lightning fast path-finding without doing anything real-time except reading data. Pre-calculate, pre-calculate & pre-calculate. That's the way AAA games do it.™ Last edited 2012 |
| ||
| Danny>>Good idea. I can run a "try to see where the player is" animation when a npc enters a new room, and during this time i have all the time i need to calculate what is the start node (near the npc) and the end node (near the player). Thanks :) Kryzon>>All you say is ok, i already use zones and i have already precalculated the links between the nodes of each zone. However when a npc detects the player, the routine must determine what is the nearest and accessible node from the npc, and what is the nearest and accessible node to the Player, and this requires a distance check and a path check (with linepick or the movement of a collider sphere). Interesting topic :) Last edited 2012 |
| ||
| What Danny and Rroff mentioned are very good concepts to always keep in mind : for AI, you don't need to calculate everything for each AI, each frame, it could be one AI per frame, or one part of an AI (sense, think, act) per frame, but the player will not notice it since there are usually 15-30 frames (updates) per second... |
   |