2

I work on a hexagon map based browser game. I have this: http://www.dark-project.cz/wesnoth/map-view/1 and now I have a problem I want to mark the fields at which the unit can go (it has limited movement). If the movement is 1 there isn't any problem but if it's higher it doesn't work right (try it).

I work with a coordinates system http://www.dark-project.cz/wesnoth/coor.png

My actual js is here: http://www.dark-project.cz/wesnoth/js/map/base.js

In other question ( Movement algorithm on a hexagon map) @unkulunkulu recommend me to use the BFS algorithm. But I have no experience with algorythms like this and its implementing into javascript and then its use on hexagon map. He say that the BFS algorithm is better for that because I can easy expand it later (add some obstacles etc.).

If you have some link to a javascript tutorial about this or something similar it will be amazing.

Community
  • 1
  • 1
Darkry
  • 590
  • 2
  • 12
  • 26
  • I'm wondering if that is the best co-ordinate system to use from the maths point of view. the zigzaging of the i confuses things to a certain extent which having the i increase over a straight diagonal (ie down and right is always +1 to i) wouldn't. However, it may be that it is less intuitive when you are looking at the map using this co-ordinate system... – Chris Jul 25 '11 at 15:55

2 Answers2

1

First, you just need to find a way to get the adjacent hexagons from the current hexagon (i,j) - the (4,3) in your picture.

This is nor hard once you realise you just need to cover two cases depending on wether the current column is even or odd:

If j is odd (j%2 == 1), the neighbours are, clockwise from the top:

(i-1, j), (i-1, j+1), (i, j+), (i+1, j), (i, j-1), (i-1, j-1)

If j is even (j%2 == 0), the neighbours are, clockwise from the top:

(i-1, j), (i, j+1), (i+1, j+), (i+1, j), (i+1, j-1), (i, j-1)

(Note that you can't create pairs in javascript using (,) notation. Perhaps having o bjects with i and j properties like {i:3, j:4} is more appropriate).

This should allow you to, given the current coordinates, find the adjacent squares and do things like coloring them or finding if a single movement is valid or not.

You will only need to use a more advanced algorithm if you need to do somehting like finding all hexes reacheable in 2 steps or finding the least number of steps to get to a certain hex.

BTW, don't just try too hard to find existing implementations of the algorithms you need in Javascript. Javascript is expressive enough that it is very easy to convert something from another language (or pseudocode) to it.

hugomg
  • 68,213
  • 24
  • 160
  • 246
  • Have you got your j is odd/j is even the right way round? for 4,3 the neighbours in order are 3,3|3,4|4,4|5,3|4,2|3,2 which matches your j is even code... – Chris Jul 25 '11 at 15:50
  • Thank you very much. This is very usefull if I want to coloring the adjacent fields but I want to coloring all hexes reacheable in 2 (or 3,4,5) steps and for it I want something more complex. Do you have some idea how to do this? – Darkry Jul 25 '11 at 15:57
1

The algotithm being suggested is roughly this:

  1. Take start square and mark it as distance 0. Add it to a list of processed hexes.

  2. Find all valid adjacent hexes (ie ones you can move into).

  3. Mark all these squares as distance 1. Add them to a list of processed hexes.

  4. Find all valid hexes adjacent to the distance 1 hexesthat are not in the processed hexes list.

  5. Mark all these squares as distance 2. Add them to a list of processed hexes.

...

X. Find all valid hexes adjacent to the distance N hexesthat are not in the processed hexes list.

X+1. Mark all these squares as distance N+1. Add them to a list of processed hexes.

The idea of the breadth first searching is that you iterate all the possibilities out from the inside so you will always find the shortest distance to each hex.

After comments from Unkulunkulu I have rethought the best implementation for this (and may change again after further input). You should have a list of processed hexes as above and also a queue of hexes awaiting processing. The unprocessed hexes list starts with just the start hex with distance 0 and you go through this list until it is exhausted. When processing a hex all new found unprocessed hexes get added to this list with their distance in. So once you have processed the distance 0 hex you should have added all the distance 1 hexes. They get processed and by the time they are done you will have all your distance 2 hexes in there...

For what its worth I think my original suggestion of recursion fails from an efficiency point of view and depending on the distance you want to go a potential stack overflow issue. :)

Chris
  • 27,210
  • 6
  • 71
  • 92
  • The last paragraph is deeply flawed, you should remove it or rewrite completely. I've never ever met a BFS implemented recursively. – unkulunkulu Jul 25 '11 at 19:37
  • @unkulunkulu: I've never really played with BFS stuff before so what I wrote above may not have been a perfect description of that. I think that the way I rewrote it is better but I am more than happy to accept suggestions on the correct way to do this and alter as appropriate... If you want to put in another answer with the information I'm more than happy to upvote it too for teaching me more stuff. :) – Chris Jul 26 '11 at 09:22