CODEWITHSUNDEEP
javascriptjquery
Darkry
Darkry

Reputation: 590

How to implement BFS for hexagon field (in javascript)

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.

Upvotes: 2

Views: 1341

Answers (2)

Chris
Chris

Reputation: 27627

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. :)

Upvotes: 1

hugomg
hugomg

Reputation: 69984

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.

Upvotes: 1

Related Questions