Movement algorithm on a hexagon map
I have a problem on this site: http://开发者_运维百科www.dark-project.cz/wesnoth/map-view/1 (click on the unit). In my Javascript source http://www.dark-project.cz/wesnoth/js/map/base.js (last $('div.unitImg').click(function()
function) I want to mark all hexagons to which the unit can't go.
I have quite a complex algorithm that works right when the movement is 1, but if it is higher it doesn't work (try movement 2).
Do you have some idea about an algorithm to find the right hexes?
Here is an example of the coordinate numbering: http://www.dark-project.cz/wesnoth/coor.png
Thank you for all replies.
At first, I suggest you redesign the coordinates. Good example is provided in this question.
But regardless of the coordinate system, I assume you'll have some obstacles on the field anyway in the future (some rocks, dragons, etc), so you should design a general algorithm prepared for that. I would suggest investigating the BFS, but you don't need to build the graph explicitly, just when you need edges, you know what the adjacent hexagons you have on your field (depth one, which is working) and traverse there. It's the general approach. There's a DFS too, but BFS is often considered more efficient for reachability problems when the number of adjacent edges is fairly limited.
精彩评论