Skip to main content
gamedev.net
🔒 Locked

Find Move Range algorithm?

Started by Grey_Havoc 5 replies 800+ views
Original Post
Grey_Havoc
Grey_Havoc
Hey guys, me again. I'm making a final fantasy tactics style game and was wondering how I would create the move algorithm. What I need it to do is show which squares the current player can step onto. This could be something like chess, for example. The player can go AROUND objects, but only if he/she has enough move points (average move being around 4). Here is an example: P is the player (move 3), x is the moveable squares, and the o's are opposing players or blocking objects (tree, bush, rock, etc.) ________________ | | | | | | | | | | | |x|o|x| | | | | |x|x|x|x|x| | | | |o|x|P|x|o| | | | |o|x|x|o| | | | | |o|x|x|x| | | | | | | |x| | | | | ----------------- how could I convert this into a quick algorithm?
http://www.brandonbarnes.us
H_o_p_s
H_o_p_s
The biggest problem that I had when trying to implement this was things like walls.

.....................x|............xx|...........xEx|x.........xxxP|xx.........Exx|x...........xx|.............x|....................... = grassP = playerE = enemyx = tile that could be moved to| = wall


The simple way that you want your algorithm would be to check every tile in the range, and if it isn't obstructed add it to a list of tiles to be highlighted for movement. But lets say there is a wall blocking right next to the player. With highlighting the range and not doing pathfinding for every tile I'm unsure how to get around this problem...
BRING BACK THE BLACK (or at least something darker)
Trap
Trap
If you don't mind some overhead:
void markmove(int movementpoints,int x,int y){if(movementpoints<=0) return;mark(x,y);if(moveable(x+1,y)) markmove(movementpoints-1,x+1,y);if(moveable(x-1,y)) markmove(movementpoints-1,x-1,y);if(moveable(x,y+1)) markmove(movementpoints-1,x,y+1);if(moveable(x,y-1)) markmove(movementpoints-1,x,y-1);}
choffstein
choffstein
EDIT: DAMN YOU TRAP! DAMN YOU TO HELL! YOU BEAT ME TO IT!

I would imagine a simple recursive function could handle this.
void markforwalk(int x, int y, int stepsLeft){   if(stepsLeft == 0)      return;   if(map[x][y] != WALL)      canWalk[x][y] = true;   else      return;   if(y+1 < MAX_MAP_HEIGHT)      markforwalk(x, y+1, stepsLeft - 1); //up   if(x-1 > MIN_MAP_WIDTH)      markforwalk(x-1, y, stepsLeft - 1); //left   if(y-1 > MIN_MAP_HEIGHT)      markforwalk(x, y-1, stepsLeft - 1); //down   if(x+1 < MAX_MAP_WIDTH)      markforwalk(x+1, y, stepsLeft - 1); //right}

Basically, this assumes you can only go up, down, left, or right. Now, lets say you have a map like this:
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][|][ ][ ][ ][ ][ ][ ][ ][ ][ ][|][ ][ ][ ][ ][ ][ ][ ][ ][|][ ][ ][ ][ ][ ][ ][-][-][-][+][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]

P is the player, - and | are walls.
So lets say this player can move 5 steps. After the algorithm, the map would look like this: 
[ ][ ][o][o][o][o][o][ ][ ][ ][ ][o][o][o][o][|][ ][ ][ ][ ][o][o][o][o][o][|][ ][ ][ ][ ][o][o][o][o][|][ ][ ][ ][ ][o][o][-][-][-][+][ ][ ][ ][ ][ ][o][ ][ ][ ][ ][ ][ ][ ][ ]

o is where the player can go.

I think that is what you want...though, maybe not. It should work the way you want.

Hope that helps.
Grey_Havoc
Grey_Havoc
thats exactly what I needed. Then if the tile is moveable it would assign the x and y variables to a dimension the size of the map (say.. selectedtiles[][])
then when the function finishes, display a blue tile where ever selectedtiles[][] = 1.

Another question.. what if I wanted to have height in my map that affects the distance between tiles. Like.. the player wants to walk from a height 1 tiles to a height 3 tile. This would cost him/her 2 of their moves (3 minus 1). Would it be hard to implement something like that?

thanks!

--Grey_Havoc
http://www.brandonbarnes.us
H_o_p_s
H_o_p_s
In mine I have a method that is 'int getHeight(int x, int y)' so I'd just do:
void markmove(int movementpoints,int x,int y){if(movementpoints<=0) return;mark(x,y);d = absoluteValue(getHeight(x,y)-getHeight(x+1,y))/2+1; // Half the height difference plus oneif(moveable(x+1,y)) markmove(movementpoints-d,x+1,y);d = absoluteValue(getHeight(x,y)-getHeight(x-1,y))/2+1;if(moveable(x-1,y)) markmove(movementpoints-d,x-1,y);d = absoluteValue(getHeight(x,y)-getHeight(x1,y+))/2+1;if(moveable(x,y+1)) markmove(movementpoints-d,x,y+1);d = absoluteValue(getHeight(x,y)-getHeight(x-1,y-1))/2+1;if(moveable(x,y-1)) markmove(movementpoints-d,x,y-1);}


[Edited by - H_o_p_s on February 21, 2005 2:20:04 PM]
BRING BACK THE BLACK (or at least something darker)
Telastyn
Telastyn
I also used the standard recursive function described by others, but use a more generic form which doesn't make assumptions about the map shape, or the number of "steps" it takes to make each move. [mostly because my map structure isn't the overused 2d array].

It also doesn't return void.

Mine returns a list of "marked" tiles rather than operating on the tiles directly [since I use the 'as the unit walks' area for other things than marking tiles]. The lists are spliced together until the entirety is returned to the caller.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.