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.

Svante
  • 50,694
  • 11
  • 78
  • 122
Darkry
  • 590
  • 2
  • 12
  • 26

1 Answers1

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.

Community
  • 1
  • 1
unkulunkulu
  • 11,576
  • 2
  • 31
  • 49
  • 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? – Darkry Jul 25 '11 at 09:03
  • 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 :) – unkulunkulu Jul 25 '11 at 09:15
  • 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. – Paweł Obrok Jul 25 '11 at 09:27
  • 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? :-) – Darkry Jul 25 '11 at 10:11
  • @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. – unkulunkulu Jul 25 '11 at 10:22
  • Now I know how the BFS go through a tree like this ( http://en.wikipedia.org/wiki/File:Breadth-first-tree.svg ) but I still don't know how to implement it on my problem. I do not think I can program this algorithm in javascript. And I don't know how to use it on my problem. How can I build some graph with relationships in HTML (look at my source code on the example)? – Darkry Jul 25 '11 at 12:21
  • @Kryštof, I mentioned twice that you should look for BFS for solving mazes, not BFS for graph or tree traversal, it's too general. – unkulunkulu Jul 25 '11 at 12:26
  • And in what direction the use of BFS will help me? Yes, i look for that but I can't find it... – Darkry Jul 25 '11 at 12:26
  • You can create a separate question like "How to implement BFS for haxagon field". But be ready to provide the actual data structure used to hold your field, the detailed description of coordinates used etc. – unkulunkulu Jul 25 '11 at 12:28