Path-finding

[/\/\isanThr0p]

Hi everybody.

I made a snakelike game in DDraw. Now I want to implement CPU enemys. So I'm thinking about a pathfinding method. I think I use A. (I'm not sure if that what I planned to do is excatly A)

Now I have no real Idea how to implement it into Code
I have an Idea, but in this Idea I'd need to start the same Sub very often, so I'll run out of stackspace!

(pseudo)code:
sub explore(x as long, y as long)
(now check out all for possible directions than give a movemtcost to them in a two dimensional array than if one of the four directions is okay call sub explore again)
end sub

I hope you understand me.
So If you can help me with an idea how to do a goodpathfinding write me!!!

Thank you

[HarryW]

I want to know too :) What the heck is A?

[/\/\isanThr0p]

A is a special method of pathfinding.
You search the way to every box and give waypoints. Then after the searsch you go from the destination back by searching the points with the fewest waypoints. (write me an email if you want to know more)

[PaulLewis]

I am interested in the challenge. I have no idea of existing and proven methods or design patterns in this area, but since it resolves to basic mathematics I don't mind helping if you need.

Let me know if you want my input. IN particular, I would need to know the goal of the "enemy". I.e. if his goal is simply to make his way out as fast as possible, or to try to cut off the player etc.

I'll be interested in the final solution too.

Regards

[/\/\isanThr0p]

It would be great to cut of the way, but in the beginning it would be okay just to get to the target (apple).

If your interested in my game i'll put the URL for download here.

Cu

[PaulLewis]

But the inputs I need would be better coming from you directly rather than me reading it from your code. Everybody (me included) always has something to say about other people's code.

If you tell me about the structure you are storing your maze in and some more details about obstacles, rules etc I can use that as input into making an "engine" or "brain" for your enemy.

If there is no maze - just wide open space with perhaps a few obstacles around, then I presume the goals of your players/enemies are:
1) stay alive the longest - by always giving yourself as much room to manoeveur as possible
2) when possible and when not in conflict with 1), cut off any opposition

I would make the enemies and players classes and then the "AI" can be tacked on to enemies. In this way, you may have several different ai's available, e.g. aggressive, conservative, chaotic, orderly etc. each enemy could have a random ai which would be more of a challenge.

All the ai's do is help the enemy decide what choice to make at each obstacle.

I hope this makes sense to you.

regards

[PaulLewis]

If you need help I have now coded a rudimentary snakes game so that I can work on the AI logic.

My "game" is graphical but not DirectX or anything. Which AI shall I do first? hehe

Regards

[PaulLewis]

This AI uses the "Instinct" Class clsInAvoidObstacles which tries to avoid any object in it's path (including apples).

This AI has a variable lookAhead value which is the number of pixels he looks in the direction of travel. The highr the value, the more twisty the travel is, especially with a high density of apples. It's quite fun to watch 10 of these AI's running around my screen... They are a bit stupid at times thoug because they tend to spiral in on themselves on ocassion...

Next I will do the one you originally wanted... The Hungry Snake AI... This one will sniff out apples to devour while trying to survive as best as possible...

I think I will have to create an Instinct for avoiding the inwards spiral problem.

If you're interested in any of this MisanThrop, drop me a line. Perhaps we can Web enable our games and let our bots (or us) play over the net.

In fact I think I will start a new topic for this...

Regards
paul.lewis@sns.co.nz

[/\/\isanThr0p]

Hey

Sorry about my absence.

I'm in the USA now for one year and I have much to do. But of course still time for programming. But you know how it is to program on somebody else's PC.

I think I can't win against your bot's because you are so far ahead against me. Do you have a maze in you game or just getting apples. Can you send me some exsamples, and do you use any messengers? Because posting in a forum is not the way to develop together.
have you ever programmed a directplay thing?
But I have an Idea I always played with. A LIFE SIMULATION. I want to do this after I found a good way for pathfinding.
If you can give me further information perhaps we can do our bot competion in some months.
What do you think about bulding a frame-program were we specify some rules and the protokol (no idea how to write this) perhaps over direct ply or with winsock. than We can make competions with many bots of others too.

Cu (next time my englsih will be clearer again hehehe)

[PaulLewis]

I made another post on that idea (bot competition).

The code I made only has apples in it. No maze as yet. After my last post, I added a few more lines of code and then got interested in something else. I started investigating winsock.

I will send you what I have so far when I add the setup form. My class model so far is like this:
Each player has an AI. Each AI has a bunch of Instincts and a bunch of Senses.

So far I have developed two Senses. These are "LookAhead" and "LookAround".

Instincts I have so far are: AvoidObstacles, EatApples, Wander. Each Instinct may also utilise one or more Senses.

Depending on the order or the Instincts in the AI's make-up, certain priorities are assigned to the instinctive results. So if an AI had the Wander and EatApples instinct, then he would happily move around changing direction 1/100 times unless an Apple was in his direct path in which case he'd override his Wander instinct and go for the apple instead.

As for the AI's:
One of the AI's is called ARROW_KEYS_AI which relates to a human player so this ai has no need to be clever.

Another AI is called "RANDOM_JUMP_AI which is just the apples. The apples are in effect set up as a player (although not a scoring player) so their "snake" is not contiguous. It just meant I could implement this ai and have it generate itself without any extra code.

Now the rest of the AI's are created with a purpose.
HOMER_AI (a.k.a. Homer Simpson - due to the stupid nature of the AI) - This one tries to be clever but seldom is. This guy has EatApples, AvoidObstacles, Wander in his "genetic code" so he usually beats the rest.

SURVIVOR_AI - tries to live as long as possible by following a simple instict. This one only has AvoidObstacles.

HUNGRY_AI - tries to avoid all obstacles except apples. His instincts are: EatApples, AvoidObstacles.

So, after that lengthy introduction, all I need to do (Or you) to implement a new AI is to develop a new instinct, nse sense, and combine them into the new AI. Then the program will be ready to use it straight away.

For an AI to figure out the path to the next closest apple, I would envisage a sense like "SmellApple" which allows the snake to smell a general direction from which the nearest apple comes from, and an Instinct called ChaseApples which would use the LookAhead, SmellApple senses as well as the EatApples, ChaseApples, AvoidObstacles Instincts.

How I'd implement the SmellApples sense is to find the nearest apple to the snake and have the AI set the snake's direction to aim towards that coordinate. This would give the effect of a "stairway" looking snake as he continually has his direction changed between the vertical and horizontal until finally he gets there. Of course, the SmellApple sense would have to be checking that the apple is still the closest...

Hmm, as I look back I see I have written a short book here :( Sorry about that. One last note though on the topic of path finding in games. In this game, I am not sure you need to determine the whole path at the start of the movement since all you really need is the next step in the journey to be worked out. It is fine to have a plan - but in a game like this where you could get blocked easily, all the processing power to pre-determine the who path would be wasted. It's much faster and better I think to do it incrementally... I hope that makes sense for you.

Anyway, email me at paul.lewis@sns.co.nz and we can discuss more.

Cheers

[/\/\isanThr0p]

STILL NOBODY ANSWERED MY FIRST QUESTIONS!

I'm searching code for pathfinding through mazes!!!!!!!!


Thanks!

ORS has a great example http://www.oneringsoftware.com/gallop called mazeit that allows you to both design and go through mazes.

[PaulLewis]

HTTP Error 404
404 Not Found

The Web server cannot find the file or script you asked for. Please check the URL to ensure that the path is correct.

Please contact the server's administrator if this problem persists.

[/\/\isanThr0p]

THERE IS NO ERRORCODE I HATE MORE!

Hey Escaflowne, I hope you can correct the URL if not I know that's not your fault! But I was so disappointed!

Thanks

:(

Sorry about that. The actual ZIP file is: http://www.oneringsoftware.com/TileTutorial.zip

Enjoy.:p :) ;) :D :rolleyes:

[/\/\isanThr0p]

Actually I can't download this zip-file, and when I try just to go to the mainpage I need a pass!

It would be really great if you could mail it to me!

Thanks for your time

I succeded building my Pathfinding, but it is still quite buggy, so I still would apreciate help!

Cu

Sure, nothing wrong with that:).

First, if you want me to e-mail you, what is your E-mail address?

That's all, and glad to help:).

[/\/\isanThr0p]

Sure!

Sorry I wanted to include it into the last post.

FGutjahr@gmx.de

Thanks!

[PaulLewis]

I'll email you my source soon...

In case it helps other people in the future, the A* algorithm is easy to implement (although the research I did seemed to try to make it sound more complex than it really is).

The idea is that for each possible move starting from the start point, you assign the potential move a rating based on various criteria. It is common to include proximity to target and movement cost (if there is any) as well as obstacle avoidance in the calculation.

This calculation (referred to as f) is how each potential path is compared with previous paths that have reached the same point.

The basic system for storing the nodes in the search is to maintain two "lists". One is called the open list and the other is the closed list.

You must ensure that the next node to check (from the open list) is the node with the lowest possible f. How you do this is up to you, but the best method is referred to as a priority queue. This is simply a storage system in which items going in are inserted in the correct place in the queue (i.e. sorted) but the only item that can be pulled out is the top one (i.e. the one with the lowest f).

The closed list is really just a means to specify that the particular node has been checked.

In the main loop, you would get the next node from the queue. Note that a node is pretty much anything you want, but normally you will want to store information in the node about the position on the map. Essential for a node is the ability to store the f value and the parent node.

Determine all legal moves. If a move is legal, attempt to add it to the Open list. When adding to the open list, first check to see if the node is already on the open list with a lower f. If it is, then do not add it, just bail out. Next, check if it is on the closed list with a lower f. If it is, bail out. If it is not on either list, or if it is, but with a higher f value, then: remove it from both lists, and add it to the open list.

Eventually your main loop will reach the end of the search space or it will reach the target - depends on what you want. For games, I recommend adding a time criteria, giving your algorithm say 1000ms to complete the search before aborting. Otherwise, on a 1000 x 1000 map, you could be looking at a few minutes to search the entire search space. Normally, this algorithm will find you the most direct route which also happens to be the cheapest in cost.

I know it's not that great an explanation, but it's a starting point for someone who has been unable to find material on the net or in their library. Basically, there is nothing too hard about it :)

Cheers

[HarryW]

Thanks for the quick explanation, very informative :)

[/\/\isanThr0p]

I knew about the basics of A* before, but not all of it!

Thanks A LOT!

I read about this on the gamasutra page. Real good page, no code!

What is this about you library? (books/cds)

[/\/\isanThr0p]

Thanks for the sample! In most cases it is impressive fast!

I couldn't get it to work in my program. everytime I was in the Debug mode it just closes! Even if I remove the ontime thing!

Thanks

(paul check your mail)

MisanThrop:

There's many ways for pathfinding, I've listed some below:


Tiling. You store certain numbers within a grid and determines their value:

Dim Matrix11 as Tile
Matrix11.Walkable = False


Coordinate Mapping. You store certain coordinates that does something special. E.G. [13y 30x to 31y 25x LoseLive 45%]

Item Destruction. You place certain controls and make these controls block your man.


Many others.