AI: Path finding and learning.

[blackcoder41]

Hi everyone, please give me ideas behind path finding. Basically I want make a program that has a maze like pacman with starting and ending point. Then the AI(player/ball) needs to find its way to the ending point. The second problem is that the AI should be more intelligent for the second try meaning bypassing dead ends that it already met.

I just need ideas, and also please tell me what field or subject of mathematics should I understand if it's going to need mathematical calculations. Advance thanks everyone :)

[Kyon]

You should check A*, it's an excellent path-finding algorithm that supports adding values per tile of how much "cost" there is to move onto that tile. If you make the cost of a dead-end hallway high enough, he will never pick it.

[blackcoder41]

Thanks, I'll check it out later. This is a self project so I don't have to rush myself. I'll post again later after reading on it. I'm still open for replies though.

[Return 0]

A* is the way to go, here's a begginers introduction: http://www.policyalmanac.org/games/aStarTutorial.htm You might also want to read up on Graph Theory.

Some more reading:
http://en.wikipedia.org/wiki/Shortest_path_problem
http://en.wikipedia.org/wiki/A*_search_algorithm

[blackcoder41]

@Kyon and Return 0
I took a little read on A* and I'll read more tomorrow and it seems to find the shortest path at one go. I was hoping something that explores the map then find its way to the end. On the second go, it then use its experience (maybe save in a file or something) to do better decision.

[rapidcoder]

A* explores the map until it gets to the ending point. Then it stops.
The power of this algorithm lies in the fact that it often doesn't need to explore the whole map, before it can be sure it has found the shortest path.

[Kyon]

Blackcoder, as I said, you can set a value per node that indicates the "cost" to pass that node. Making an earlier visited node have an infinite "cost" will mean that this particular node cannot be visited (because it is dead end).

[hamsterman]

I was hoping something that explores the map then find its way to the end. On the second go, it then use its experience (maybe save in a file or something) to do better decision.

Well, the closest solution to that is to generate a graph that is more simple than the map. That would make this algorithm slightly faster. Unless your map can change.
But that isn't needed at all. A* isn't as slow as it may seem.

[PiMaster]

If you want it to learn from experience, you could try a neural network.

[blackcoder41]

@PiMaster
Yeah that's what I want to do but after reading a little about it, it seems like it's more difficult to implement :(

@All
Thanks to you all, at least I was able to learn about A*

[NGen]

Right, now a practical game-oriented implementation of some AI would give some room for error by the AI rather than creating an absolute shortest-path solution. How would you put in this error exactly?

[blackcoder41]

I'm not actually making a game. It's just one day I wake up and I wanna do this learning AI thingy. The AI that I was thinking does not necessarily choose the shortest path. Hence it should make better decisions after some learning, that may or may not lead it to the shortest path.

If ever you know some information that could help please let me know. Thanks :)

[Kyon]

That would mean an abstract algorithm involving the fact that the AI does not know about potential paths, but does "observations". Rather, he only observes that which he can logically know. A simple way would be something like:

AISTEP()
   Look ahead.
   If road ahead contains the exit
       Empty all queues
       Take the exit
   If entire highest-level road queue is impassable
       Remove highest-level road queue and go back one level
   Else if road ahead is dead-end (has no corners or splits)
       Go back and take a different road
       Remove current hallway from checking queue and mark it as impassable
   Else if road ahead is not dead-end
       Add all splits and corners to the potential road queue
       Take the first road
       AISTEP()

A road queue is a n-dimensional container of roads that can contain other road queues.
This is not completely fleshed out, but all I could come up with on the spot.