As: Non Tile-based Pathfinding 2005-07-26 06:01:18
id recommend you read this (even if it isnt explained very well) to get an introduction to pathfinding, i wont go into any detail about how the algorithm works as it is the exact same algorithm used in my tile-based pathfinding topic, instead this is simply an extension on how to use it in a non tile-based world
the links between pathnodes determine the paths that can be taken, in a tilebased world the links are done like this (red are links)
however since the nodes are placed unevenely (usually anyways) in a non tile based world and not place in rows and collumns then the links can be arranged like this:
the advantage of a non tile based arrangement is that alot less nodes are needed meaning a faster and less laggy engine.
in the tilebased algorithm, it checks all the tiles surrounding the current one being searched, in the non tilebased its simply a case of checking all tiles that are linked to it.
you could do this by storing a list of linked nodes in each pathnode.
the problem with a non tilebased world is the links between the nodes, they are tedious to do and to place the nodes correctly and diong it manually listing the linked nodes could take hours, the only realastic way to do this automticly is to loop through every node and trace a ray of that node to every node and test for collisions and that its actually walkable, this way all the the links can be done by the computer and links can also be found from anywhere in the world.
by tracing a ray i mean that you test every coordinate along the link testing for collisions and walkability
the last thing to mention is that in the tilebased world the cost of moving from one tile to another is the horizontal distance (in my examples it was one to go with the map), in the non tile based world the cost of moving from one tile to the other is just the distance from one node to the other, for this you can just use pythagoreus's theorem - hyp^2 = sum of the other 2 sides (or 3 sides for 3dimensions) squared. ie the distance is the sqrt of the x difference squared add the y difference squared.
the cost of the nodes for different types of terrain can be used as follows, when finding the cost for moving from one node to the other, the best way to do it would probably be to add the terrain cost of the two nodes on that link.
(this usest ot be more fully explained but i accidently closed window and couldnt be bothered to rewrite it all)
here is an example of a non tilebased pathfinder (click on a node to find the shortest path to it)
im giong to work on a better example now.
again, anyone wanting me to explain anything a bit better that you dont understand or i havnt explained well, please ask