<+><+><+><+><+><+><+>
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 >>
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)
===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 ***
*** 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
