CODEWITHSUNDEEP
phpalgorithmvectormatrix
swalter88
swalter88

Reputation: 1413

Searching for matrix way finding algorithm

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

Upvotes: 2

Views: 275

Answers (2)

Jens Schauder
Jens Schauder

Reputation: 81882

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'

Upvotes: 1

Nick Pickering
Nick Pickering

Reputation: 3185

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.

Upvotes: 0

Related Questions