Find possible 'path'

[Jorick]

Hello everyone!

 

I'm working on a tiled RPG game. You know, the type of game where you're in a world built out of tile images. Picture about any old GameBoy game. You can see the game board as a grid with tiles you can move on, and tiles you can't move on.

 

This is very simple to do when you only allow them to go up/down/bottom/top, one at a time. However, I want to make a system that lets them click any tile visible on the screen, and not only the adjacent ones. The problem here is that there are a lot of situations where you can't logically reach the tile that has been clicked, because it is surrounded by tiles that you can not walk on. (Eg: You are on one side of a fence, and the fence door is not on your screen)

 

Does anyone know of a clever and efficient way to find a possible path between the tile of the player and the destination tile?

 

Thank you in advance,

-Jorick

[Gekk0]

This sounds similar to a chess program i've been working on (well currently shelved due to other projects), but i think the basic principle is the same... Basically.... what you'd want is a like a chess board, but with only the king's movements

 

this is it:

 

http://sandbox.squarecirclestudio.com/chess/

 

I'm not sure if its really the most efficient way... i'm doing it, i wrote it after a drunken competition with a couple mates that we could design a chess playing computer  ....yes we're a little geeky =P

 

Basically what i do is

 

- create a "board array" which has 64 elements, numbered from 1 (top left) to 64 (bottom right).. this denotes every square on the board

 

- create an array of pieces, with elements like this $pieces[1]['type'] = 'r';  .... so this one means the piece located at square 1 (top left) is type Rook...

 

- then i have a function with figures all of the possible movements that the piece say, located at square 1 can perfom, and in this function it checks whether there is another piece in the square its trying to move to and whether that piece is a friend or foe... its a foe we can take it, a friend we cant move there

 

- i think whats relevant for you is this, when i'm figuring out the movements, what i'm doing is using a loop like this

 

	//y axis moves
	for($i = ($loc + ; $i < 65; $i = $i + 
		{

		if(isset($pieces[$i]) && $pieces[$i]['colour'] != $pieces[$loc]['colour'])
			{

			$moves[$i] = 2;

			break;

			}

		if(isset($pieces[$i]) && $pieces[$i]['colour'] == $pieces[$loc]['colour'])
			{

			break;

			}

		$moves[$i] = 1;

		if(isset($lim))
			{

			break;

			}			

		}

	for($i = ($loc - ; $i > 0; $i = $i - 
		{

		if(isset($pieces[$i]) && $pieces[$i]['colour'] != $pieces[$loc]['colour'])
			{

			$moves[$i] = 2;

			break;

			}

		if(isset($pieces[$i]) && $pieces[$i]['colour'] == $pieces[$loc]['colour'])
			{

			break;

			}

		$moves[$i] = 1;

		if(isset($lim))
			{

			break;

			}

		}

	if($pieces[$loc]['type'] == 'r')
		{

		return $moves;

		}

	}

 

so i'm taking the location number of the piece, and basically say, adding/subtracting 8 from it (this is for y axis movements), untill i "hit" either the end of the board or another piece, then i figure if its friend or foe, and then i stop.

 

 

I'm not sure if this is helpful, or i've explained it very well... the program is about 440 lines long in the end... but there are probably more efficient ways... i did it kinda drunk soooo

[beta0x64]

The name will scare you, but investigate the concepy of a neural network. If you can make each tile its own "neuron," you can determine where your character is and the next available place closest to your destination, the next available place closer to the destination, the next, the next, and so on. This is also good for coding in a "discovery" system, kinda like any RTS where there is a fog of war.