You may notice that I changed my coordinate system so that the Y axis is skewed, which makes calculating ranges and stuff a bit simpler and faster than my previous 'squiggly' Y axis. Although I did program a working distance algorithm with the squiggly axis, it is certainly faster with a skewed Y axis. The only problem is that the map area is now diamond shaped rather than nice and rectangular. I may lop of the pointy corners to make a hexagonal shaped map area, which I guess is more appropriate anyway. The compressed map for network transmission will still be efficient enough.
I also implemented a Dijkstra algorithm version which is used to highlight the valid movement destinations for a selected creature. The player can simply tap/click on a highlighted hex to move there. It will also be possible to tap/click on an enemy to move and attack it with one command.
The next step is to issue a movement command from the client, validate it on the server, and implement a movement animation on the client side. After that I will add implementation for some of the more complex aspects of movement - engagement to enemy creatures and enemy creatures as move/attack targets.
Hexes! The one true map format.
ReplyDeleteYes, having X and Y at 120 degrees worked better for me as well. I invented the W direction as well - if I'd been smart it would have been at 120 degrees to both of them, making them a barycentric triplet (i.e. X+Y+W=0), but instead I put it between them (60 degrees away from each) which isn't as pleasing, and now I'm kinda stuck with that convention. Ah well. It's a purely symbolic thing anyway, and never stored anywhere.
I read some article where some guy had a 3rd axis, which made distance calculations easier, but didn't bother with it.
DeleteThe third coordinate essentially transforms a hex grid into an isometric cube grid, taking a “slice” out of it where x+y+z = 0. Cube grid math is simple like square grid math, so there are times when this is handy for simplifying hex grid algorithms. As Tom mentioned you don't actually store the third coordinate but you can calculate it (z = -x-y) only when it's useful. One of these days I should write a blog post about this.
DeleteNice work. You may want check one of the best resources about pathfinfing/binary seach and also hexes grids for later reference:
ReplyDeletehttp://www-cs-students.stanford.edu/~amitp/gameprog.html
I have also this series bookmarked for a deeper approach:
http://harablog.wordpress.com/2011/08/26/fast-pathfinding-via-symmetry-breaking/
http://harablog.wordpress.com/2011/09/01/rectangular-symmetry-reduction/
http://harablog.wordpress.com/2011/09/07/jump-point-search/
But anyway since Chaos grids are relative small you probably won't need go further.
Very interesting stuff! The Chaos grids are indeedpretty tiny, so I don't expect more complications.
DeleteIn Chaos Grove I only used Dijkstra because when you let the player move the mouse over the highlighted squares (found from Dijkstra) you already have the parent information to do path finding to any of those squares. No additional A* needed.
ReplyDeleteHope that helps.. :)
Yeah, for the player its no problem. The only use I would have for A* with heuristics pathfinding is for the AI to head towards distant targets - but even then an expanded Dijkstra might be even better, in order to compare the value all possible targets.
DeleteThe screenshot has also addressed another issue that I was wanting, which is in Chaos battle mode, I want to see all of the board in one screenshot without having to scroll around. (Theres a Gold Dragon behind you! Oh no there isn't! Oh yes there is!) And also not too much perspective, so the distances towards the back of the appear much the same as those at the front. I don't know if the Unity engine provides an orthogonal camera view.
ReplyDelete