The source files
Hey,
I promised in one of my posts that I would be posting the source files… So here they are!
Note that these classes are the last stable build. I have newer classes but they aren’t tested completely.
All sugestions, optimisations, comments, etc are more than welcome !!
Download: A* Source Files
-Enjoy!
July 21st, 2006 at 3:17 am
I haven;t had a chance to mess with your Astar code yet, but I am very interested in using it in a hexagonal board (center point with 6 possible positions to move - so there are technically no diagonals). I have managed to convert Zeh’s code to handle this without much trouble and was wondering if you can provide a heads up or any advice if I was to try and implement it into your code.
Great work!
- Matt
July 21st, 2006 at 9:01 am
Hi Matt!
I hope you won’t have much trouble adjusting the code… I think the only thing you will have to change, is the ‘findSurroundingTiles’ method (line 403).
An array is created with the name ’st’ and that array has to collect all the tiles that are connected to the given tile (@argument current).
I don’t really have experience with how to build a hexagonal board, but you will probably want to add ‘top left’, ‘top right’, ‘right’, ‘bottom right’, ‘bottom left’ and ‘left’ to the st array ?
Since you wouldn’t have diagonal tiles anymore, you can probably just delete the if(clippingmode == “semi”){ } else { } and add all those tiles anyway.
So my guess is, it would be something like this:
–
private function findSurroundingTiles(current:Tile):Array
{
var st:Array = new Array(); //st = surroundingTiles
var x:Number = current.x;
var y:Number = current.y;
//check left, right, down left, down right, up left and up right. Check: walkable & not closed
var yxd:Tile = map[y][x-1]; //xd = xdown
var yxu:Tile = map[y][x-(-1)];//xu = xUp
if(yxd.walkable && !yxd.isClosed() )
{
st.push(yxd);
yxd.costDown();
}
if(yxu.walkable && !yxu.isClosed() )
{
st.push(yxu);
yxu.costDown();
}
var ydxd:Tile = map[y-1][x-1];//ydxd = yDownxDown
var ydxu:Tile = map[y-1][x-(-1)]; //ydxu = yDownxUp
var yuxu:Tile = map[y-(-1)][x-(-1)]; //yuxu = yUpxUp
var yuxd:Tile = map[y-(-1)][x-1]; //yuxd = yUpxDown
if(ydxd.walkable && !ydxd.isClosed())
{
st.push(ydxd);
ydxd.costDown();
}
if(ydxu.walkable && !ydxu.isClosed() )
{
st.push(ydxu);
ydxu.costDown();
}
if(yuxu.walkable && !yuxu.isClosed() )
{
st.push(yuxu);
yuxu.costDown();
}
if(yuxd.walkable && !yuxd.isClosed() )
{
st.push(yuxd);
yuxd.costDown();
}
return st;
}
–
Good luck :).
July 28th, 2006 at 4:11 pm
Wow! Thanks for the detailed response. Actually I think I got it working - it was much easier than I thought. A hexagon board is basically a 9 position grid, minus either the two top diagonals, or two bottom diagonals, depending on the row number. Here’s what I did:
In the Astar.as file, I edited the private function findSurroundingTiles to include the following statement:
else if (clippingMode == “hex”) {
//check left-up, left-down, right-up and right-down on alternating grid pattern + walkable & not closed
// check for hexagon grid offset - if an even column, check bottom right and left hexes
if (x % 2 > 0) {
//var ydxd:Tile = map[y-1][x-1];//ydxd = yDownxDown
//var ydxu:Tile = map[y-1][x-(-1)]; //ydxu = yDownxUp
var yuxu:Tile = map[y-(-1)][x-(-1)]; //yuxu = yUpxUp
var yuxd:Tile = map[y-(-1)][x-1]; //yuxd = yUpxDown
if(yuxu.walkable && !yuxu.isClosed() ) {
st.push(yuxu);
yuxu.costUp();
}
if(yuxd.walkable && !yuxd.isClosed() ) {
st.push(yuxd);
yuxd.costUp();
}
// check for hexagon grid offset - if an odd column, check top right and left hexes
} else {
var ydxd:Tile = map[y-1][x-1];//ydxd = yDownxDown
var ydxu:Tile = map[y-1][x-(-1)]; //ydxu = yDownxUp
//var yuxu:Tile = map[y-(-1)][x-(-1)]; //yuxu = yUpxUp
//var yuxd:Tile = map[y-(-1)][x-1]; //yuxd = yUpxDown
if(ydxd.walkable && !ydxd.isClosed()) {
st.push(ydxd);
ydxd.costUp();
}
if(ydxu.walkable && !ydxu.isClosed()) {
st.push(ydxu);
ydxu.costUp();
}
}
}
You can see the rough idea here: http://www.mattgyver.com/flash/astar_pathfinding_tweaked.swf
Hexagon flash pathfinding sample
Thanks again! My next quest is to calculate a general search area and return all possible spaces without any actual end point. like if my player can only move 10 spaces, show me all the possibilities taking into account the map array x,y value (terrain height) value.
- Matt
July 28th, 2006 at 4:22 pm
Looks cool :).
About your next quest: I don’t know if you already know this or not, but you won’t be needing A* for that…
In fact, the algorithm isn’t that hard at all…
From the top of my head:
-find start tile-add all neighbour cells to an open list
-set total cost and parent for each cell
-start while (openlist > 0)
-set the first cell from the openlist to 'currentCell'
-if the neighbour cells are already in open list
-check if the cost of the path to that cell through this cell is lower than the cost it already has
-else
-add to openlist, set cost & parent
-end else
-set currentCell to 'closed'
-end while
I think that would do it :).
Ps: I just made these steps up, so I don’t know if there is a known algorithm for this… (There probably is).
July 28th, 2006 at 4:24 pm
I forgot to switch out the costUp() to a costDown() in my code because all movement has equal weight.
July 28th, 2006 at 4:48 pm
I figured since it needs at least some degree of pathfinding; parents, g, h, and f and whatnot, I was going to try and fit it into the current code as another function like showRange() where it taps into the open list where current movementCost
July 28th, 2006 at 6:14 pm
Bah - it cut off my last post. You get the idea. [rolling up sleeves] this is going to get messy…!
June 25th, 2007 at 12:28 pm
be.dauntless.Astar.BinaryHeap
line 46:
var t:Number = heap[Math.floor(cp/2)];
do “t” really supposed to be number? trace(t) always returns NaN… (AS3)
do you updated your algorithm? would be lovely to see latest version
June 25th, 2007 at 4:54 pm
You’re right, that should be ‘var t:Tile = …’
I haven’t modified the AS2 files, but I am going to write an AS3 implementation :). (Which is going te have more features).
June 25th, 2007 at 7:21 pm
Can’t wait, i think you will notice more problems
keep up good work.