It’s been a while since I’ve written anything related to path-finding, so I figured I would take the opportunity to re-learn A* (this time with more programming experience under my belt). The heuristic uses a tile-count estimate, and not a straight-line distance (so much more accurate for the hexagonal grid). I came away with a much better understanding of how the algorithm actually works and finished my path-finding base for a tower defense game I’m working on.
For now the only real optimization is that it caps the maximum new paths at 10 per frame, so if you have 250 units on screen it’s not trying to find new paths for them all at the same time. Next I plan to do the obvious optimizations for a TD (cache the “main” path and reset it whenever the map changes), as well as do optimizations with finding nearby paths instead of each unit finding it’s own path (so multiple units on the same hexagon, or directly next to one another share a single path-finding call).
Anyhow, just thought I’d post here since I’d never posted anything in the showcase before and it’s kind of neat to play with
Left-Click places the start square
Shift-Left-Click places the finish square
Once those two are placed creeps will start to spawn. After that, you can use Ctrl-Left-Click to toggle walk-ability on the hexagons (green = can walk, gray = cannot). You cannot block the main path, however - you can block off individual creeps for now. You can move the start/finish any time.
Anyhow, enjoy - an actual tower defense game is in the works now and should make it’s way to the showcase in stages.
Sure. I started by creating a hexagonal cylinder in Maya to be my base object, then instantiated them like this:
_tiles = new List<MapTile>();
_tileDict = new Dictionary<MapPoint, MapTile>();
float spacingX = _mapSpacing * Mathf.Sin(Mathf.Deg2Rad * 60);
float spacingZ = _mapSpacing * Mathf.Sin(Mathf.Deg2Rad * 30);
for (int i = 0; i < _mapCols; i++){
for (int j = 0; j < _mapRows; j++){
GameObject thisNode = Helpers.InstantiatePrefab("Prefabs/Tiles/testTile");
Vector3 thisPosition = new Vector3(0, 0, 0);
thisPosition.z = _mapSpacing * j;
thisPosition.x = spacingX * i;
// This tile is odd
if ( (i 1) == 1 ){
thisPosition.z -= spacingZ;
} else {
}
// TODO: This really needs to be cleaned up
int rowMod = 0;
if (i >= 2){
rowMod = i;
if ((rowMod 1) == 1){
rowMod--;
}
rowMod = rowMod / 2;
}
thisNode.name = i.ToString() + "," + (j + rowMod).ToString();
thisNode.transform.position = thisPosition;
thisNode.transform.parent = _mapBase.transform;
thisNode.renderer.material = _normMat;
MapTile thisTile = (MapTile)thisNode.GetComponent(typeof(MapTile));
thisTile.Init(new MapPoint(i, j + rowMod), 1);
_tiles.Add(thisTile);
_tileDict.Add(new MapPoint(i, j + rowMod), thisTile);
}
}
It’s not particularly elegant and I’ll definitely be cleaning it up here soon, but for now that’s how I space out the objects themselves. If you’re interested in why I assigned the X/Y coordinates the way I did, it makes finding neighbors easier (I’m attaching a quick image I made as a reference for my hexagonal grid system).
Not sure why this thread never highlighted again for me! But Thanks for offering this explanation up. I use a very similar strategy for my cube based grid.
At any rate, great job so far, it’s looking great.
Is there any chance you would be willing to share your A* path-finding code?
I am completely new to unity, and I am loving it, and I had to register to the forums right after reading your post.
I am struggling with this stuff too, and I would love to be able to learn from it .
Some where else I had read that, another team tackled the problem by turning each hex into tri’s and then used Bresenham’s algorythm.
