# Simple pathfinding?

This topic is 2573 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

So I have a map, each and every character on the map is saved in a char array [x][y]

I have walls INSIDE the map, not just around the edges. The first debug map didn't have this though...

So originally, I just had checked whether the X coord or the Y coord was farther away, then made the monster move in that direction at a 75% rate, 25% rate to move in a random direction. (This way you CAN avoid the monsters... somewhat)

Anyway, I then added in walls, so there was details inside the maps.

So now the monsters just run into walls...

How could I make the monster find the most ideal path to the character, and then walk that path at a 75% rate?

Also, on a completely unrelated topic...

How do I create a tictactoe AI? I currently have many MANY if's...

##### Share on other sites
http://en.wikipedia.org/wiki/Tic-tac-toe#Strategy

If you just follow that it's pretty simple.

##### Share on other sites

http://en.wikipedia....ac-toe#Strategy

If you just follow that it's pretty simple.

That has no code on it. Just tells me how to play tic tac toe lol. I have studied tic tac toe for many years, and can win at a 92.7% rate against somebody who has never played against my strategy.

My problem is, I can't figure out how to take those millions of if statements and make it one for loops, or 4 cuz there's 4 different directions it can win in...

##### Share on other sites
What you are looking for (for your monsters) is A*. It is the first step along the AI development path but should suffice your needs to get your monsters finding the character. I used the details under this link to build my A* library.
Also for tic tac toe, when I first wrote it I had a mountain of if statements as well. The last time I wrote tic tac toe though I changed it so the positions that define a win are in an array, and I just iterate through them check if all 3 values match. Went from having a couple hundred lines of logic to about 20 that does the exact same thing.

int [,]winningIndexes = new int[,]
{ 0,1,2},
{3,4,5}
};

etc...etc.

** EDIT added in loop example***

Then you iterate through like so;

for (int i = 0; i < 8; i++) {// there are 8 possible ways someone can win, horizontals, verticals and 2 diagonals.
if (board[winningIndexes[i,0]] == board[winningIndexes[i,1]] && board[winningIndexes[i,1}] == board[winningIndexes[i,2]]) {
// we have a win, do something
}
// otherwise continue looping.
}

Hope this helps.

##### Share on other sites
HOLY ****** **** ********* **** ***** ******* *** ** *******

That's confusing. LOL.

I think I understand it though.

When I load the map, I assign two variables, G[y][x] and H[y][x]

And when I move my player, I also update the H value of every H variable on the map.
Then, when the computer moves, I check the surrounding areas, up/left/down/right (No diagonals in my game.) to see which one has the least F[y][x] value
F[y] [x] = G[y] [x] + H[y] [x]

if the surrounding area is equal to '|' or '_' or some other non walkable space, then ignore that space.

And that's basically how it works?

##### Share on other sites

HOLY ****** **** ********* **** ***** ******* *** ** *******

That's confusing. LOL.

I think I understand it though.

When I load the map, I assign two variables, G[y][x] and H[y][x]

And when I move my player, I also update the H value of every H variable on the map.
Then, when the computer moves, I check the surrounding areas, up/left/down/right (No diagonals in my game.) to see which one has the least F[y][x] value
F[y] [x] = G[y] [x] + H[y] [x]

if the surrounding area is equal to '|' or '_' or some other non walkable space, then ignore that space.

And that's basically how it works?

Yeah it can be very confusing, took me about 4 reads through that article before I got something working and than many, many hours debugging code. I believe that article includes his example source code (although I never looked at it) so you might want to download that. It sounds like you have most of it down though with a couple small misconceptions. The whole map isn't assigned G,H or F scores. The way the algorithm works is it basically starts at you and moves out in a square (or in your case a t pattern because you aren't allowing diagonals), and will continue this pattern until reaching the goal. Also when the player moves you do not update the H scores of the pieces (I suppose you might be able to do it that way....not sure), usually you will just re-search for a new path at specific intervals/waypoints or even every update() (but this is generally not needed).The whole board will not assign G/H/F score values (unless there is no path to the end from the start) because of this pattern, it only searches as far as it needs. I found that article very useful but it will take a couple reads to fully grasp it. You sound like you are on your way.

Hope this helps.

##### Share on other sites

[quote name='XDaWNeDX' timestamp='1307038160' post='4818780']
HOLY ****** **** ********* **** ***** ******* *** ** *******

That's confusing. LOL.

I think I understand it though.

When I load the map, I assign two variables, G[y][x] and H[y][x]

And when I move my player, I also update the H value of every H variable on the map.
Then, when the computer moves, I check the surrounding areas, up/left/down/right (No diagonals in my game.) to see which one has the least F[y][x] value
F[y] [x] = G[y] [x] + H[y] [x]

if the surrounding area is equal to '|' or '_' or some other non walkable space, then ignore that space.

And that's basically how it works?

Yeah it can be very confusing, took me about 4 reads through that article before I got something working and than many, many hours debugging code. I believe that article includes his example source code (although I never looked at it) so you might want to download that. It sounds like you have most of it down though with a couple small misconceptions. The whole map isn't assigned G,H or F scores. The way the algorithm works is it basically starts at you and moves out in a square (or in your case a t pattern because you aren't allowing diagonals), and will continue this pattern until reaching the goal. Also when the player moves you do not update the H scores of the pieces (I suppose you might be able to do it that way....not sure), usually you will just re-search for a new path at specific intervals/waypoints or even every update() (but this is generally not needed).The whole board will not assign G/H/F score values (unless there is no path to the end from the start) because of this pattern, it only searches as far as it needs. I found that article very useful but it will take a couple reads to fully grasp it. You sound like you are on your way.

Hope this helps.
[/quote]

OK. I think I get it. I don't have any code to work with right now, but I'm sure I'll get it right away when I get home.

I want to move the computers AI.

So in the computermove function, I use a function called getmove()

In THAT function,
I assign a mark to the squares which are unwalkable.
I find the g/h variables of the squares in a 't' around me, as long as they DON'T have that mark.
I then ADD those two variables together to get the f variable.

I compare however many variables I got to find which F is the smallest.

Then return a number saying which move is most ideal.

My game is NOT realtime, so the computer only needs to move the one time.

##### Share on other sites
no, if you do it that way then you will end up with the same result as you got before - monsters running into walls and getting stuck. You need to find the ENTIRE path to the character, each turn/movement in order to find the correct 'next move'.

##### Share on other sites

no, if you do it that way then you will end up with the same result as you got before - monsters running into walls and getting stuck. You need to find the ENTIRE path to the character, each turn/movement in order to find the correct 'next move'.

Ahh, missed that part of the logic...

I'll TRY and implement that now. But that little bit makes it a LOT harder. Meh, I'm sure I can figure it out once I get to requiring AI. (Still working on the battle sequences)

##### Share on other sites
You can do a floodfill from the player(s) to mark the real distance of each square to the player,
then each monster takes "randomly" a square according to the value of the square.

• 48
• 12
• 10
• 10
• 9
• ### Forum Statistics

• Total Topics
631375
• Total Posts
2999660
×