Array A* Path-finding for a turn based game

Post your own tutorials, guides and demos.

Post » Mon Jul 09, 2012 4:24 am

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 whats going on:

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 dont 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 isnt a problem. But lets say you have a map of 250x250( a large map in age of empires) thats 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 diedmaybe 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 havent 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 Im 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 Ill 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 findingBartosh2012-07-09 04:37:14
Posts: 249
Reputation: 2,323

Return to Your tutorials & example files

Who is online

Users browsing this forum: No registered users and 0 guests