Jump to content
  • Advertisement
Sign in to follow this  
XDaWNeDX

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.

If you intended to correct an error in the post then please contact us.

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 this post


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

If you just follow that it's pretty simple.

Share this post


Link to post
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 this post


Link to post
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.
A* link.
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!