A Game Map // advanced PHP problem...

xconspirisist

Hey there. This will be an extremely long post/thread, consisting of some relitivly advanced concepts. I'm really not sure if it can even be done. Any help is massivly appreciated.

I'm working on a project, called 'prog'. Its a RPG style webpage based game, focusing on php/sql as a backend. Imagine it to be something quite like the gameboy zelda games, shining force, things like that.

The problem, is with the 4x4 map, which looks something like this;

The naming system for the individual cells are as follows;

This map is generated via a very basic mysql table. Another table holds details concerning the current position of a player on the map. Now imagine the following scenario;

I would like the player to move to a position on the map by a simple click on the cell. In the diagram, the user is at 2.2, and needs to get to 4.4. Clicking on each cell adjacently, I can code a system that moves the player via basic update querys. However. I would now like for the player to click this cell, 4.4, and have some php code work out the shortest route, and then take it automaticly, trackling the number of cells traversed in the interrim.

Along with this, some cells are not travesable, imagine cell 3.3 is not, in the example above, this means the route would have to be 3.2, 4.2, 4.3, 4.4.

The problem, is that I cant even think of any psudo code, even, in order to get started, and I very much need many third opinions.

Many thanks in advance, any considerable help will definatly be included within the project credits file and other places where appropreiate.

justsomeone

What you're talking about sounds like maze traversal. This is a classic in algorithm design. Search for "Maze traversal".

Put briefly, you decide on a basic "next move" strategy to be used when deciding where to go next from any given square. In a maze where each square has 4 potential options (arbitrarily called North, South, East, West), you might set up your "next move" algorithm to be something like:
1. Try going left (and explore from there)
2. Try going straightahead (and explore from there)
3. Try going left (and explore from there)

With a vanilla maze problem, you just keep going until you reach your goal. But you want to do something slightly more complicated, keeping track of the "cost" of any given route.

So, from any position to any adjacent position, you may have a cost associated with it. You can set this up any way you like, maybe a cost of 1 is the normal, but you might have a cost of 2 if that direction is "uphill" or 0 if it's "downhill" - according to the geography of your map. A cost of 9999 would effectively mean that there is no route.

The "(explore from there)" in the description above is the clue that this is a recursive algorithm.

I'm not going to paste any code in here, but depending on the complexity and your time pressures, I might be able to turn something around in my spare time - no promises though. Chance are, I won't be able to do this quickly enough for you.

ahundiak

If the maze is never going to be bigger than 4x4 then you might also consider just storing the best path for a given source/destination pair. Figure out the path either manually or by using one of the algorithms suggested by justsomeone.

I know having the non-traversable cells will make things more difficult depending in part on how many possible combinations of NT cells you will have.

One possibility is to store several routes for each combination then check each route to see if it's valid for a specific layout.

Edited: because I accidently got justsomeone's name wrong. Oops.

justsomeone

"justsomeTHING"?!!

I have a nickname now?

Coool!