Be a Supporter!

As: Non Tile-based Pathfinding

  • 4,340 Views
  • 10 Replies
New Topic Respond to this Topic
dELtaluca
dELtaluca
  • Member since: Apr. 16, 2004
  • Offline.
Forum Stats
Member
Level 20
Blank Slate
As: Non Tile-based Pathfinding Jul. 26th, 2005 @ 06:01 AM Reply

AS: Main

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

You should probably read this before hand

the links between pathnodes determine the paths that can be taken, in a tilebased world the links are done like this (red are links)
tbased.jpg

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:

ntbased.jpg

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)

NOPATH.swf

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


using ShamelessPlug; NapePhysicsEngine.advertise();

BBS Signature
Inglor
Inglor
  • Member since: Jan. 26, 2003
  • Offline.
Forum Stats
Member
Level 17
Blank Slate
Response to As: Non Tile-based Pathfinding Jul. 26th, 2005 @ 06:02 AM Reply

I'll bet you 10 dollars this will be linked less then 5 times :P

it took me a year of algorithmics to understand that sort of algorithem:P

nice work nontheless

dELtaluca
dELtaluca
  • Member since: Apr. 16, 2004
  • Offline.
Forum Stats
Member
Level 20
Blank Slate
Response to As: Non Tile-based Pathfinding Jul. 26th, 2005 @ 06:04 AM Reply

lol,
oh and in the NOPATH, the nodes highlighted red are the ones that are actually searched


using ShamelessPlug; NapePhysicsEngine.advertise();

BBS Signature
liam
liam
  • Member since: Dec. 11, 2004
  • Offline.
Forum Stats
Member
Level 22
Blank Slate
Response to As: Non Tile-based Pathfinding Jul. 26th, 2005 @ 07:28 AM Reply

At 7/26/05 06:04 AM, dELta_Luca wrote: lol,
oh and in the NOPATH, the nodes highlighted red are the ones that are actually searched

Thought so, excellent tutorial again too.


Sup, bitches :)

BBS Signature
dELtaluca
dELtaluca
  • Member since: Apr. 16, 2004
  • Offline.
Forum Stats
Member
Level 20
Blank Slate
Response to As: Non Tile-based Pathfinding Jul. 29th, 2005 @ 05:58 AM Reply

well ive been on working on this for a few days:

NOSPATH.html

explanations on how to use are shown for each radiobutton at the bottom; there are a few glitches that will happend everynow and again but otherwise it does work, i made this sample really to give a better hands on approach for the non tile based pathfinding and also to demonstrate the ray tracing technique (also used in line of sight and lighting) for dynamic nodes like the player and target but just to make it easier as you no longer have to identify the links yourself.


using ShamelessPlug; NapePhysicsEngine.advertise();

BBS Signature
dELtaluca
dELtaluca
  • Member since: Apr. 16, 2004
  • Offline.
Forum Stats
Member
Level 20
Blank Slate
Response to As: Non Tile-based Pathfinding Jul. 29th, 2005 @ 06:22 AM Reply

also, note that the player and the target are nodes themselves so its not neccesary to place the path nodes in every little bit thats accesible, the best way to lay the nodes is to describe the fastest fastest around the map making sure that that all places are in view of a path node

like i said you sometimes get some glitches the main one being that everynow and again depending on position of nodes and position of target and player, the player might start moving through walls, if this happens try a few more times moving it around and either just refresh or re do the path nodes around where the problem area is


using ShamelessPlug; NapePhysicsEngine.advertise();

BBS Signature
Tolomus
Tolomus
  • Member since: Nov. 17, 2005
  • Offline.
Forum Stats
Member
Level 07
Blank Slate
Response to As: Non Tile-based Pathfinding Apr. 1st, 2006 @ 03:04 PM Reply

Hey all...

I know this is an old thread... but oh well.

Firstly, this is an excellent tut... however, for people (like me) who would actually like to make a Flash game including non tile based pathfinding, this tut, while very interesting, doesn't deal with the actual code used in your examples (particularly the one where you said you had worked for a few days).

If it isn't too much trouble, could you (or someone who understands non tile-based pathfinding) explain in more detail the construction of the code for your examples? It might be too much to ask for a source file for the examples (not for just copying, but for understanding and using the code) but is it possible to post some or all of the codes used in the last example file here, with explanations behind it all?

Thanks in advance...

James

Tolomus
Tolomus
  • Member since: Nov. 17, 2005
  • Offline.
Forum Stats
Member
Level 07
Blank Slate
Response to As: Non Tile-based Pathfinding Apr. 1st, 2006 @ 05:37 PM Reply

Bump.... anybody?

dELtaluca
dELtaluca
  • Member since: Apr. 16, 2004
  • Offline.
Forum Stats
Member
Level 20
Blank Slate
Response to As: Non Tile-based Pathfinding Apr. 2nd, 2006 @ 04:45 PM Reply

At 4/1/06 03:04 PM, Tolomus wrote: bladibla :P

well this tutorial is an extension upon my tile-based pathfinding tute linked at start. As im pretty sure ive said, its the exact same algorithm, only instead of each tile being linked to adjacent tiles, you have each node being linked to a list of nodes defined in a list. The rest of the changes are explained.

Im not going to release any source, because i believe a tutorial should only teach rather than show


using ShamelessPlug; NapePhysicsEngine.advertise();

BBS Signature
dELtaluca
dELtaluca
  • Member since: Apr. 16, 2004
  • Offline.
Forum Stats
Member
Level 20
Blank Slate
Response to As: Non Tile-based Pathfinding Apr. 2nd, 2006 @ 04:51 PM Reply

lol i sort of contradicted myself there, not realising i posted source code to the OPath.swf in my other tutorial :p nevermind :X but anyways, that source has the actual algorithm itself (although only for tile based, but like i said this is an extension on tile based)


using ShamelessPlug; NapePhysicsEngine.advertise();

BBS Signature
Tolomus
Tolomus
  • Member since: Nov. 17, 2005
  • Offline.
Forum Stats
Member
Level 07
Blank Slate
Response to As: Non Tile-based Pathfinding Apr. 3rd, 2006 @ 12:41 PM Reply

Thank you very much for your responses...

I understand your reluctance to realease the source codes (as you said you did for the Tile based, but I understand what your saying if you don't want to release the non tile based one)...

I've read both your tuts on Tile and non-tile based... also a link I found somewhere to explanations of A*... and I also agree with you that tuts should teach rather than show, however... I understand the principles of the A* and the principles of pathfinding, but I'm not very advanced in AS... so while I understand what your saying (i think) in your tuts, what I do not understand is the actual implementation of these principles in Flash AS.

I'll be trying, I guess, to understand the source code you posted in the tile based tut (of course, if you don't mind).

Anyway thanks for your responses... :)