My A* path finding system using arrays:
A Star Wizzard
Extremely quick and supporting terrain movement costs.
Pay attention to witch array is in the condition and event.
I use a separate array:?ls? to search the main array.
For a better understanding of what?s going on:
policyalmanac.org/games/aStarTutorial.htm
big thanks to R0J0hound for the pathlist generation in his a*system.
the movement is purely orthogonal, but that was intentional, for a turn based strategy system, however, it would be easy. if not easier. to switch to checking diagonally also.
----------------------------------------------------------------
Why Custom Path finding?
The Rts behavior is great. Its one of the big reasons I started using construct. However its limitations are rather large, and doing a custom path finding system allows for all kinds of good stuff.
Such as:
Roads/swamps. The Ai preferring to travel on one terrain, while trying to avoid another
Generating small localized paths. So you don?t have to check the whole world to go 5 feet.
Abstract path finding. Think the maps off of Escape velocity, or a platform based rts.
Being able to find just the next wave point in a path.
Avoiding other objects paths, so no clusters unless necessary.
-----------------------------------------------------------------------
Why arrays?
Using arrays allow for data to be stored and called without the need
For objects ? at all.
this is great for:
1. Large maps
Construct has issues with storing large amounts of sprites.
No mater what, even if its not being called. if an object exist it gets check
On a small scale, this isn?t a problem. But lets say you have a map of 250x250( a large map in age of empires) that?s 62500 objects getting checked to see if they do anything. That adds up and causes massive dips in frame rate.
The only viable way of supporting large maps is to dynamically generate the terrain based on if the player sees it. However the rts movement with construct need objects to exist in order to avoid them. Using an array to move, this is not an issue.
2. Independent of the program
All types of possibilities come about by having things moving and interacting in nonexistent planes. Including the possibility of 3d terrain (think dwarf fortrice). Or inside buildings (Zelda LTTP style). Or path in other places away from the current layout ( Like x3)
3. Easy porting to any kind of node system
Traditional, Isometric, octagon, ext.
Just change what nodes in the array are checked and how they correlate to other objects
4. Fits perfectly witch custom tile maps
Chances are if your doing tile maps, your probably doing them with an array already. Instead of trying to ham fist in the rts behavior, have the game find its path using your map array.
5. Rts commander Ai.
Advanced ai can be made by assigning weight to the terrain based on if units get killed on that terrain. Simply put, if everybody went that way and died?maybe we should go elsewhere.
6. Map generator roads
Roads can be built based on the terrain, as opposed to just blasting thru everything.
7. Easy to save
Just an event.
Save array? done.
--------------------------------------------------------------------
I haven?t spent much time with the latest a* path finding systems using objects others have made. (they came out while I was working on this) but I?m fairly certain using arrays will be faster, just by virtue of how construct handles sprite objects.but I could be totally wrong:)
As far as using this for your own projects, just copy and paste away. But if you come up with something awesome using this as a starting point, share it with the community. Were all in this together.
-------------------------------------------------------------------
My next project is a doosey , so im breaking down each complex component before stitching them all together. As I do I?ll release each as a tutorial.
On my to do list of A* tutorials:
layout independent path finding( wizard position and variables stored in array also)
Multi unit path finding
3d path finding
Escape velocity style map path finding