2

i am developing a board game in php and now i have problems in writing an algorithm...

the game board is a multidimensional array ($board[10][10]) to define rows and columns of the board matrix or vector...

now i have to loop through the complete board but with a dynamic start point. for example the user selects cell [5,6] this is the start point for the loop. goal is to find all available board cells around the selected cell to find the target cells for a move method. i think i need a performant and efficient way to do this. does anyone know an algorithm to loop through a matrix/vector, only ones every field to find the available and used cells?

extra rule... in the picture appended is a blue field selected (is a little bigger than the other). the available fields are only on the right side. the left side are available but not reachable from the current selected position... i think this is a extra information which makes the algorithm a little bit complicated....

big thx so far!

kind regards

Improve this question
2
  • Might be more approprate on gamedev.stackexchange.com Commented Feb 22, 2013 at 9:35
  • 1
    didnt know that this site exist^^ but makes sense Commented Feb 22, 2013 at 9:39

2 Answers 2

Reset to default
1

not completely sure that I got the requirements right, so let me restate them:

You want an efficient algorithm to loop through all elements of an nxn matrix with n approximately 10, which starts at a given element (i,j) and is ordered by distance from (i,j)!?

I'd loop through a distance variable d from 0 to n/2 then for each value of d loop for l through -(2*d) to +(2*d)-1 pick the the cells (i+d, j+l), if i>=0 also pick (i+l,j-d),(i+l, j+d) for each cell you have to apply a modulo n, to map negativ indexes back to the matrix.

This considers the matrix basically a torus, glueing upper and lower edge as well as left and right edge together.

If you don't like that you can let run d up to n and instead of a modulo operation just ignore values outside the matrix.

These aproaches give you the fields directly in the correct order. For small fields I do doubt any kind of optimization on this level has much of an effect in most situations, Nicholas approach might be just as good.

Update I slightly modified the cells to pick in order to honor the rule 'only consider fields that are right from the current column or on the same column'

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

3 Comments

Much more impressive than my solution. If N grows larger unexpectedly, I would have a problem. ;] +1
i think i dont get it^^ sry. did this respect the problem with the left and right side i described above?
It now does consider the additional constraint.
0

If your map is only 10x10, I'd loop through from [0][0], collecting all the possible spaces for the player to move, then grade the spaces by distance to current player position. N is small, so the fact that the algorithm has O(N^2) shouldn't affect your performance much.

Maybe someone with more background in algorithms has something up their sleeve.

Improve this answer

2 Comments

theres a extra rule i forgot to write... i will edit the main comment
You still have to sort the fields if I got the requirements right, which would add another nlogn factor to the complexity.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.