## AS: tile-based pathfinding

• 4,265 Views
• 6 Replies
dELtaluca
dELtaluca
• Member since: Apr. 16, 2004
• Offline.
Forum Stats
Member
Level 20
Blank Slate
AS: tile-based pathfinding 2005-07-25 13:27:03

As: Main

<+><+><+><+><+><+><+>
Tile-based Pathfinding

ive been tryign to think of something to do for the AS: stuff and finnaly thought of something - pathfinding, im only going to concentrate on tile-based pathfiding for the moment - i may or may not go into more complicated pathfinding wuch that doesnt rely on a tile based system but on path nodes.

the algorithm im going to discuss is called the A* Algorithm and before we start - here is a quick sample of what can be achieved. << I made this on the 4th October 2004 >>

PathFinder.swf

S is the Start, T is the Target, using the number keys you can add walls (6) with numbers 1-5 being varying 'slopes' which are harder to pass over meaning that the path found finds the 'best' route which might not always be the shortest.

here is another which is bit simpler to understand. (click anywhere and the player will move to it)

OPath.html

===The A* Algorithm===

#Each node has cost value of travelling on it for example in my OPath example the cost of trvaelling over the nodes is shown in the tile

#the sub cost in the algorithm is the portion of the cost which comes from the movement cost added to the node cost

#the hueristic is the estimated cost to get to the target - in my examples it is the distance from that node to the target (if the hueristic is too high then the path will be unnacurate - if its too low then the engine will not run as fast - a good balance is needed)

>>An open list is created originailly with only the current node inside

while the openlist isnt empty ##

>>choose the node in the open list with the lowest cost
>>from this node search all nodes connected to it
>>>>if its the target then end the loop ==>> goto END:
>>>>if its cost value is greater than 0 (in my OPath the walls are -1)
>>>>>>determine its cost: Parent nodes sub cost + movment cost + node cost + hueristic
>>>>>>if it hasnt yet been searched OR the new cost is lower than the old cost
>>>>>>>>write the cost with sub cost and parent to the node and if it hasnt been searched yet at it into the openlist

##if it is empty then the path list is empty and the target is unreachable

END:
>>from the target node - loop backwards through each nodes parent until you get to the start adding the node into the path list
>>reverse the path so it goes from the origin to the target:

((( as you might be able to see im not too good at explaining things )))

Source code to the OPath.swf (note that the contents of the as file are actually just on the first frame. infact ***

OPath.as

*** if you wanted to crete your own using this script

create a movieclip with 2 frames, on the first have a dynamic textfield - var name 'dif'
then the second frame the same but with a semi-transparent box behind it (25*25)

another movielcip with just a circle of sometihng around 17*17

for each the registration point should be in the centre -17.5 so that its containted in a 25*25 box at (0,0) [damn thats badly explained]

the first with linkage as 'tile' and the second as 'player'

and either copy and paste the contents or include it on the first frame

there are many things you can add to improve this: one thing ive done in the past is to extend on the algorithm in flash so that it would never lagg no matter what size a search area (up to flashes memory capabilities that is) with a constantly updated path such that is shown in this: (which runs 3x faster in flash player than in the browser)

use arrow keys to move
smarterpath2.html

IF theres anyuthing you want to try and explain better ask me (im sure you will since im crap at explaining stuff) the source code should i hope make things clearer

Inglor
Inglor
• Member since: Jan. 26, 2003
• Offline.
Forum Stats
Member
Level 17
Blank Slate
Response to AS: tile-based pathfinding 2005-07-25 13:34:26

you could have at least linked to

AS: Tile Based Game Development.

dELtaluca
dELtaluca
• Member since: Apr. 16, 2004
• Offline.
Forum Stats
Member
Level 20
Blank Slate
Response to AS: tile-based pathfinding 2005-07-25 13:36:08

didnt know it existed sorry.

Inglor
Inglor
• Member since: Jan. 26, 2003
• Offline.
Forum Stats
Member
Level 17
Blank Slate
Response to AS: tile-based pathfinding 2005-07-25 13:36:59

lol ok ;)

anyhow, leave a link to this in AS: Main

nice algorithem btw

liam
liam
• Member since: Dec. 11, 2004
• Offline.
Forum Stats
Member
Level 22
Blank Slate
Response to AS: tile-based pathfinding 2005-07-25 13:43:48

Impressive..

Very nice indeed.

Sup, bitches :)

dELtaluca
dELtaluca
• Member since: Apr. 16, 2004
• Offline.
Forum Stats
Member
Level 20
Blank Slate
Response to AS: tile-based pathfinding 2005-07-25 13:47:55

thx... oh yeh, also.

this algorithm can also be extened to diagonal movement aswell simply be check the nodes diagonally also (perhaps with an error checking for clipping against corners)

and can also be extended to 3d dimensions for multifloored buildings etc

http://delta.ecwhost..ltifloored-step2.swf

its a bit hard to udnerstand whats going on at first - the 3 sets of tiles are the 3 floors of the buildings, the white tiles are the floor, the black tiels are walls, and the grey tiles are stair cases or lifts or whatever

Rustygames
Rustygames
• Member since: May. 7, 2005
• Offline.
Forum Stats
Supporter
Level 19
Programmer
Response to AS: tile-based pathfinding 2005-07-30 14:29:57

This is a really confusing tutorial and is much better if you already grasp a bit of knowlage into the whole A* algorithm thing I STONGLY reccomend this because it is VERY helpful (then make sure you come back here for a good overview and an AS example)

Also inglor this isnt necessarily used for tile-based games (just the pathfinding is tile based) (if that makes sense) so he shouldnt really need to link back there