# Simple pathfinding?

## 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
[quote name='H4VK' timestamp='1307036511' post='4818764']
[url="http://en.wikipedia.org/wiki/Tic-tac-toe#Strategy"]http://en.wikipedia....ac-toe#Strategy[/url]

If you just follow that it's pretty simple.
[/quote]

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.
[code]
int [,]winningIndexes = new int[,]
{ 0,1,2},
{3,4,5}
};
[/code]
etc...etc.

** EDIT added in loop example***

Then you iterate through like so;
[code]
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.
}
[/code]

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
[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?
[/quote]

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='XXChester' timestamp='1307039158' post='4818788']
[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?
[/quote]

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
[quote name='leopardpm' timestamp='1307057305' post='4818900']
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'.
[/quote]

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.

##### Share on other sites
[quote name='Jarod42' timestamp='1307088238' post='4818966']
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.
[/quote]

Is that NOT what A* is?

##### Share on other sites
Hmmm...

Wouldnt it be like twice faster if you raycasted from the player and the monster at the same time, and get the path when the 2 floods meet each other (if they meet)?

And if you added a point wich you know the monster will have to go through, it would get even faster?

Just wondring because all A* stuff ive seen just pathfind from the AI, wich makes it have to pathfind a lot bigger area... Though actually getting the path the faster way might be a tiny bit more complex :|

##### Share on other sites
A* and tree search respectively. 2 of the most well-documented, "intro to AI" topics out there.

##### Share on other sites
I didn't suggest A* by any means because it is the fastest, I suggested it because he was looking for a way to move his enemies...meaning he has no previous AI knowledge and I firmly believe A* is a great introduction.

##### Share on other sites
As I understand your question, there is a percentage to "follow" the path.
FloodFill visit more square than A*. (but if you have several monster, you can use One FloodFill vs several A*)
But you can use real distance to choose in which square to go.
for example, you can go 50% to the best square, 25% to the second, ...

##### Share on other sites
It's also possible to implement A* so that multiple agents can reuse the distance and heuristic scores for each explored node, provided they have the same movement characteristics and destination node in the graph (which could be the case for multiple AI monsters trying to get to the player, for example). It's a great exercise in applied caching, actually.

##### Share on other sites
Unless his map is spectacularly huge, speed is not even remotely going to be a problem.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628370
• Total Posts
2982300

• 10
• 9
• 13
• 24
• 11