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.

Improve this question
1
  • 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... Commented Jul 25, 2011 at 15:55

2 Answers 2

Reset to default
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. :)

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

2 Comments

The last paragraph is deeply flawed, you should remove it or rewrite completely. I've never ever met a BFS implemented recursively.
@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. :)
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.

Improve this answer

2 Comments

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...
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?

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.