Sorry your browser is not supported!

Some basic info about A* algorythm:
It is designed to work on a coordinate grid (tiled matrix in our case).
So we start search from some Start tile abd store next tile in the array. Also we store 'Cost' of the tile (each tile can be set to have different pass priority during path search process) and finally 'Weight Function' of the tile (wich uses 'Cost' value and used to determine final tile passage priority). And so on till bound tiles array is empty:
- Get tile from array wich can be reached with minimal problems
- If this tile is End tile - exit
- Check all 8 aligned tiles of the current tile. If aligned tile isn't wall - perform all calculations (Cost,WF...)
- Store all passable bound tiles of the current tile in an array

Some common notes:
- This project contain many different things but the main purpose of this project was to create optimized Path Finding algorythm
- A* algo realization is far from optimized i think because there is some methods exist to optimize original A* algo
- Please feel free to modify this project to get optimal path finder

Some algorythm note:
- It is non optimal for a 3D space path finding because movement path is very rough and looking unreal... Need to soft movement between waypoints!
- It will pass between 2 walls if movement is one of SW,SE,NW,NE. Dometimes it might be looking as object justwalking through the objects...

So! Any suggestions are welcomed!

http://darkbasicpro.thegamecreators.com/userdata/codebase/files/Astar_path.rar

Hi,

A while ago I tried to do an A* pathfinder but my problem was that my character would sometimes walk own a dead end corridor and hit the end.

This was because technically the end of the corridor would be closer to the target point and hence the character would walk down and hit the end instead of taking a longer but successfull route round the corridor.

Have you managed to fix that?

Good work, although it's a little difficult to see what's going on with the 3D view. It would be nice to have a top-down view too



Avoiding this isn't too difficult really. When you are stepping diagonally, you just need to check the adjacent cells to see if they are clear. You can do this simply by checking the cells at (CurrentX, NewY) and (NewX, CurrentY). If both of them are blocked then you simply treat the cell as blocked during that iteration.

Suggested optimisations:

- You use a straight-line guess for the distance still to travel. Using a 'manhatten' distance is more efficient, and a produces the same results. You simply add the x and y differences together.

- You are doing the same thing that everyone else has done for A* when you maintain and search your open list (except me of course ).

You are using a simple array, and searching from the start to the end to find the lowest cost cell to check next. This is a very costly way to do it.

Firstly, your lowest cost cells are usually at the end of the array, so you are constantly choosing a new lowest-cost cell.

Secondly, you have to search the whole array every time.

Thirdly, you never remove items from the array, so it always gets more expensive to search as you go on.

I suggest that you take a look at understanding and using a heap for your storage. This will give you a massive speed-up when getting the next lowest-cost cell.

Basically if you have 1000 items in your open list, your method will search all 1000 items for the lowest cost cell, and then leave that cell in the open list (meaning that the list always grows).

If you use a heap instead, then the lowest cost item is always the first item in the array, and removing it will only take up to 9 comparisons and up to 9 moves of data. Also, the heap will only ever be as big as it needs to be. If the number of items doubles, then this will add a single extra comparison and move to the removal operation.

You can check out both my heap example code and my A*/flood search routines in the CodeBase to see how it works in practice. There is a url in the description of the heap code that has a great explanation of how heaps work.

Heap : http://www.thegamecreators.com/?m=codebase_view&i=604edc86c5cdb7db3d4d2681729356b0
Pathfinding : http://www.thegamecreators.com/?m=codebase_view&i=56984d6fa64dd67ceb1e01c8d835c957

@DavidT,
If you dead-end when there is actually a path to be found, you are not using true A*. If there is a path, A* finds it.

Perhaps David was using some sort of depth search.

Thanks for some info to think about! -)

IanM: i will examine your sources (just downloaded) and wil try to upgrade my version of algorythm. Also i want to ask you: can you describe me some methods to get rid of useless waypoints in the final path? For example, if there is 5 WPs in a straight line, it will be right to get rid off 3 useless waypoints and leave only 2 KEY WPs. I think it might be a good idea to remember what WPs is 'change direction' WPs and rid off the others. But there are too many snaky diagonal paths, so this method isn't optimal.

David T: You can change camera view with a HOME key and use MIDDLE mouse button to adjust angle of view.

this is an a* pathfinder for dbpro i attempted a while back after reading about it. it seems to work but its not quite right - you can give it a simple path and it makes hard work out of it..

arrowkeys move the yellow selector block
u for wall
s for start position
f for finish position

enter to find path

let me know what you think!

@RobK:

I was simply checking the distance to the end for each surrounding tile and moving to the closest tile. I might try the true version next time

@Tom:

Thanks

Huh? Where did Rob post?

@PantheR RIP,
I don't really see the point in removing those 'extra' waypoints. IMO, the memory taken up by them isn't worth worrying about, and the extra trouble of detecting and removing them would slow the final path-build down slightly. In my code, there are 12 bytes per waypoint (2x4 for the x and y, plus 4 for the array pointer).

Anyway, if you don't agree ( ) then there is a fairly simple way of detecting an unnecessary waypoint.

Calculate the x and y difference between the previous waypoint and the current one. Then calculate the x and y difference between the current waypoint and the next one. If they are the same then the current waypoint is not needed and can be removed

Oops hehe - I get you two confused :p

TPC, Flintstones. That's all I have in terms of reference material

Yeah. That one may be all what i need! I need only those waypoints that is directional ones...

IanM: I've tried to examine your source code, but it is very complicated for me ( Damn... Am i so stupid? I can't understand how the Heap routine works!

I think i need to recalcuate path finding each time another waypoint reached... This is for the recognition of the dynamicaly moving objects and to avoid them.

Try this link instead : http://www.policyalmanac.org/games/binaryHeaps.htm