0

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.

Improve this question

1 Answer 1

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

Thank you for the answer. I never work with such complicated things and algorytms. Until now I just program some applications in PHP (like e-shops, complex comunnication web of some club - used OOP) and in javascript also only some easier things. So I have no experience with algorytms like BFS and their implementing in JavaScript. Do you know any tutorial about this algorytms in js and their application on this problem or something similar?
Unfortunately, I don't know the links, because I was learning that in school in russian, so I can't provide a trusted link to an english resource. You could google that. I can suggest you try to find not the general graph algorithm(as linked wiki page), but some examples of finding an exit from a maze using BFS. It will give you some insight I believe. It's quite easy if you don't think about graphs too much, but about knights and dragons and/or mazes instead :)
BFS is very natural here as it makes sure that nodes are traversed in order of increasing distance so it can be easily modified to only find nodes which are some fixed distance away.
Thank you. Until now I was looking for some example of use BFS in JavaScript or at least BFS implementation to javascript but I could not find anything. Actually I dont know what I'm looking for :-). It will be some javascript function or library and I will use it like other function and give it some parametres? :-)
@Kryštof, no, the BFS is quite easy to write on your own, so you should look for an example, then understand it and apply to your task.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.