A*Star Pathfinding With GE

[Cleve_Blakemore]

There is a way to do. I have it working but it needs to be broken up into pieces that can be done as stages so the computations don't slow down the game when running concurrently with character behaviour.

Create a blank array of point structures (two integers) with some added fields:

struct PATHPOINT
{
int x;
int y;
int distance;
}

Now create two arrays of these points - one to hold points for pathfinding and another to hold the resulting path. The first should be bigger than the second, but you'll have to be the judge of how big is enough for your game requirements.

Search in a circle at say, 16 angles starting with a distance of 10 pixels. (You'll have to adjust this figure to customize it to your game). Use the safe actor function to see if your actor can occupy this space projected at X, Y and ONLY add that point if they can. Keep doing this in a circle and extending the distance until you are within a given distance of your destination and can reach it from that point. You have now found your target and have to find the most efficient set of point nodes back to your origin.

Count back through the array you've created, scanning the array each time from the destination to find the closer distance to your origin and the closest distance to current path node. Each time you find just such a cell and it is the closest to the current cell, store it in the second array and bump up your counter of the elements in use in that array.

Now you've hit your origin, you're ready to start your character walking on this path. Step backwards through the path list of cells, giving your character a MoveTo command to each one. When you reach your destination, you have implemented pathfinding in Game Editor.

Optimizing the pathfinding routine and getting it to work cooporatively in DrawActor without slowing your game down is a different subject, especially when many concurrent actors are doing pathfinding. I am still working on my routine to make it faster and more efficient.

[Fuzzy]

One might use marker actors; invisible actors with stored paths to at least one other marker.

It might be more efficient to have the marker actors have clean line of sight to other markers, and then you jsut need an angle and distance in each one.

[Cleve_Blakemore]

I tried this method originally, it worked but I decided it was memory inefficient and could be done by a simpler route.

Tell me what you think of this method.

I know the upper corner of my map and abstract this into a grid I represent in the global code of 32x32 cells. By iterating through all the solid clones on the map (building renderings) I can use the rectangle that results to mark some of the cells in the array as walkable, others as solid.

Once you've got this grid, you can now "spread the pool" of incrementing numbers in the grid until you reach your destination. At first I was using 45 degree increments but changed this to 20 because it seemed to eliminate a few bugs. Then I went to 8 directional checks because it was faster at the expense of making the resulting path rougher.

I have this working but with some caveats. It only works for one actor at a time, sucks up a lot of processing (I'm trying to do it in steps) and results in a slightly rough path - although a second alg could smooth it out. I added a path array of up to 40 ints to each actor to store the path, so the pool of actors can use the global array to figure out a path to something then store their paths locally.

I need this to be working to do a proper isometric game. If you tinker with it long enough you can get nearly anything working pretty well for your time invested in Game Editor - in my experience so far. It's almost like trying to get the most speed out of my C64 using hybrid basic-ML programs years ago.

Of course what would really make this method rock would be Makslane adding the capacity to build your own path for a character at run-time and then assign it to him - that would be awesome. That would at least automate the movement once you figured out the path.

I am also going to change the "solids" grid into an array of bitfields to conserve space.