AI trouble

[rEaL iGoR]

I have a tilemap 20*15 and have created a house with two rooms
it looks something like this:

---------------------
| | |
|room1| r |
| | o |
|--- ---- o |
| m |
| 2 |
|--------------------


I've created a simple AI that makes i Circle move from til X to tile Y
very easily. But I have some problems making them move so that they avoide the wall. Can anybody help me? please?

In advance, thank you very much

[rEaL iGoR]

oops

The 'Room' became quite a mess


### ################
# # #
# # #
# # #
# # #
# # #
# # #
## ### #
# #
# #
# #
#
# #
# #
####################

This is how it really looks

[kedaman]

Do you need the path to be the shortest or, is the circle "searching" it's way while it's walking. Is the circle detecting walls or does it have the map memorated?

[rEaL iGoR]

The Computerplayed Person/Character/Whatever should be able to find the shortest path possible in every situations. Which means that wether it's this map or any other, my 'Thing' should be able to move wherever he wants, or...I want

[/\/\isanThr0p]

What you need is the A+ algorithm. You can search for that on the net. I will try to find an example someone gave me. It was very good, I just didn't really manage to incorporate it into my app, so I don't know if I still have it. I have a look.
But go ahead and search some pages for examples.

[Jotaf98]

You could also use Dijkstra's path finding algorythm:

http://64.23.12.52/tutorials/GM_Dijkstra.htm

But I'm not sure if if it's efficient in a tile engine.

[rEaL iGoR]

your link does'nt seem to work. You have a better one?:confused:

[Fox]

Search www.gamedev.net for the A* alogrithm

[Jotaf98]

Oh well... anyway, search the web too for "Dijkstra" and "Path-finding". It should work :)

The best of all is that it's a very fast algorythm, compared to others ;) But I never tried the A* (or A+ -- how do you spell it, Fox? :p ) algorythm, so I'm not sure.

[DarkMoose]

You could be somewhat lazy like me and just make yer AI's avoid walls altogether =D For me it's just easier that way instead of doing all that annoying collision detection all over again ^^ Well I just hope I never come to a point where I need one of my townspeople to walk around a corner =)

[rEaL iGoR]

You know, this is extremely bothering. I still have'nt figured it out. The A*-thing should probably solve it, however, I've read a lot of stuff on the net, and not one single of the web-pages actually explaines how to use iot or what it really does. Just a few notes, some C-coding(Which link doesn't appear to work, of course) and that it is a good algorithm for pathfinding. Not very soon, I'm gonna give up, which by the way is very sad, cause it's somehow my philosophy that 'Never give up'! But this problem takes the cake. I can't plunder on this anymore, or I'm going quite insane. And that wouldn't be too good, cause suddeny, I'll find myself eating my computer.

YUMMY, a nice CPU is just what an empty stomach need!

So please, does anyone have something that would help me out? It would REALLY be great!

[Zaei]

A* is fairly slow, but it works. What you need is to have your map in a 2D array of booleans, with FALSE where you can walk, and TRUE where you cannot. I believe that if you use recursion, you can check the values around the point you are located at, and as long as the next square is a) FALSE and b) closer to the destination, add that to a list of way points. when you reach the destination, play back the list of way points, and there you go.

Another method draws a line from the start point to the destination point. If it intersects with anything, add a point to the path so that at least one of the 2 points can see it. if the remaining path is still blocked, add a point so that point can see the new point. if the path from the 2 middle points is still blocked, add a new point so one of the two can see it. Etcetera, etcetera, etcetera.

The second method is the better of the two, but still could easily be improved upon. Get comfortable with recursion =P.

Z.

[Zaei]

And for some reason, the "Subject" box is always filled with "Mr" all the time....

Z.

[hypnos]

I believe waypoints is probably the best idea. They use them in most 3D shooters.

[Jotaf98]

Well if he's using a tile engine, he'd have to build the waypoints manually for every map...

[rEaL iGoR]

And that is exactly my problem. I want people to be able to create maps for their selves. Waypoints are difficult that way

[Brykovian]

Have you looked at these links?

www.gameai.com/pathfinding.html


-Bryk

[Brykovian]

Also, here is a VB-related path-finding starter ...
voodoovb.thenexus.bc.ca/pathfinding.html

The guy who wrote it (Rag-on-a-Stick) is writing the AI/Pathfinding for the community game "Darkness Rising", found here:
www.atypical-interactive.com

He may be a source of help for you ...

-Bryk

[Zaei]

My method generates the waypoints on the fly. All you have to do is build in suport to test if a line goes through a wall.

Z.

[kedaman]

Complex maps (that is have lots of wall corners) adds up more nodes. Open areas with lots of surrounding walls are dangerous, the amount of links can become impossible due to permutations. Some algoritms have a way to cope with that but has it's own drawbacks (it is said?), I haven't encountered any though (if anyone knows, let me know).

I've thought of considering BSP a good solution, for maps with low amount of nodes (or relatively sparse) but irrelevant amount of links allowing huge spaces without being a drawback for speed and especially memory. If a partition contains no walls it doesn't need to be further partitioned either. Between two sisterpartitions, the shortest way from two points is straight. Between two aunt-related partitions the shortest way can be both straight and pass trough the nephew's sister. Between two higher level related points pathfinding is delegated via common mother, starting delegation at closest daughter partition. If neither daugthers fails the pathfinding problem is raised onto the common mothers mother. If she doesn't have a mother, there is no connection between the points.

[Jotaf98]

Hum have you tested that theory? :)

(No I didn't get most of what you said, sorry :p )

[kedaman]

No, I'm just speculating as I said :) just for implementing on my own game, goes nice since I need BSP anyway.

[Jotaf98]

Heh well, as that guy says in GameAI.com : "I personally detest over-analysis of anything" :p

[Zaei]

a) Has anyone ever been able to create an AI that can over analyze anything?
b) Is it even possible to over analyze something?

Z.

[Brykovian]

Originally posted by Zaei
a) Has anyone ever been able to create an AI that can over analyze anything?
b) Is it even possible to over analyze something?

Z.

a) Yes ... through poor coding, a game's AI can very easily analyze things it doesn't need to (therefore, over-analyzing) ... this is one way to create an overly slow, inefficient AI routine

b) First answer: Yes -- read kedaman's posts :D j/k, man! :D ...

b) Second answer: Um ... yes. It's whenever the little voice in the back of your head starts to whisper "get a life" ... It happens to me on occasion ... I usually ignore it.;):D

Enjoy!

-Bryk

[Zaei]

a) I disagree. An AI may analyze the wrong thing, but you can't call this over analyzing, in much the same way as you cannot call a man going to the supermarket "over-eating" =).

b) I dont think the little voice is telling you that you have over analyzed something, but perhaps i should rephrase the question... "Is it possible to over analyze something that is worth analyzing?"

Z.

[kedaman]

I'm not quite sure what that means actually. The idea i was pondering on was more like the opposite, trying to avoid the permuation problem as well as cutting of memory issue with large empty areas. If you mean analyzing as in building up the node tree or in my case partitions, there's a specific reason for doing so.

[Brykovian]

Originally posted by Zaei
a) I disagree. An AI may analyze the wrong thing, but you can't call this over analyzing, in much the same way as you cannot call a man going to the supermarket "over-eating" =).

b) I dont think the little voice is telling you that you have over analyzed something, but perhaps i should rephrase the question... "Is it possible to over analyze something that is worth analyzing?"

Z.

a) Okay, Z ... I see your point. However, if that man looking for food stops at a hardware store first, just in case they might sell candy bars at a lower price than the grocery store ... oh, never mind ...;)

b) In answer to both of your ways of asking the same question: Yes. Firstly, I'd say you may have over-analyzed when you've lost your sense of humor about something.:D Secondly, if you spend a *lot* of time in order to find the "best practice" while a "pretty darn good practice" could be found in 1/10th the time -- you may have over-analyzed ... Now, once the "pretty darn good practice" is in place, I'm all for having someone continue on the analysis to make things better ...

Anyway, I think I may have already spent too much time on this one ... cheers.

-Bryk

[Jotaf98]

I'm not quite sure what that means actually. The idea i was pondering on was more like the opposite, trying to avoid the permuation problem as well as cutting of memory issue with large empty areas. If you mean analyzing as in building up the node tree or in my case partitions, there's a specific reason for doing so.


LOL! :D

Sorry keda, but I was talking about your speech... you talked about the theory instead of giving us working code. People usually don't like that kind of stuff... probably because it's boring. It doesn't mean yours isn't a good idea. It's just that, under these conditions, we can't understand it clearly... :rolleyes:

You two (yes, Brik and Zaei): Over-analysis means 'too much babling and nothing moves' (sort of like when someone shows you a computer program that he/she says is great, but you don't get to see something). Hope that clears everything :p

[kedaman]

no action, just crap-talk, i c what you mean ;)

on the subject, kinda hard to get the stuff you want because it's just such stuff that is hard to get.

[Jotaf98]

Yeah, you should probably stick with the A* algorythm. That's what I'm probably gonna do anyway :D

[Zaei]

A* is actually fairly slow. It searches ALL nodes in the search space, using, i believe, an oct-tree, until it finds the ending location. This is just the implementation that I saw, that came with GPG I, but still....

Z.

[Brykovian]

From what I've seen on A-star, you can adjust it with a heuristic (usually something like "d * n", where d is the direct distance between the points and n is a constant > 1 and < whatever would be likely to be to far for the application) ... this will stop the routine from searching the paths that are obviously too far.

Now, this may result in no path found ... so I've seen routines that start n being small (1.25, or so), then iteratively increase it until either a path is found, or until all spaces have been searched. This can take a while, so it needs to be broken into quick bits until a conclusion is found.

Also, the search tree is dependent on the legal moves available from cell-to-cell.

:pAnd, I'm sorry that I don't have any code to show ... I just haven't ever found a good VB example, and I haven't had to write my own yet ...:D:p

-Bryk

[Jotaf98]

Hey, if anyone finds the perfect path-finding code, post it here! ;) :D

[kedaman]

perfect, for what purpose?
btw, i found GSL templates on the gameai.com you mentioned, looks very good, general purpose and allows you to design your algoritm as well as node and edge properties :)

[Illuminator]

In my experience I have found three main pathfinding problems

Graph - a set of nodes and paths are already given. Very easy to solve using a depth first search algorithm.

code formulation:
given an adjacency list, the depth first search follows a path from the start until it can not go any further. It stops because it reaches a node it has visited before or it reaches the destination. You then back up the path to the last decision and follow a new path as far as it goes. You keep track of the total distance travelled until all nodes have been traversed. This algorithm can be modified for easy AI giving the process only a certain amount of time to find a path. Once a time limit is hit you take the best path found in that time.


Vector - You have a region to traverse in which walls represented as vectors(start point, and end point) You are allowed to go anywhere without crossing walls. ie you are not limited to tiles.

code formulation:
You would first create an adjacency list (on the fly for AI) This is done by taking your starting point as node 1. The next node will be a corner of a wall that you can go around. (ie your position does not fall within the anlge made by two joining walls) It also helps to extand the node along the line travelled to get past the edgeof the wall. You then repeat the process until you have found the destination or all nodes have been traversed.

Gradient - moving in certain directions has a cost related to the distance traveled. This is commly used in terrain traversal.

code formulation:
Draw a straight line between taget and destination. Calculate total time to traverse line. Break the line in a number of sub lines. At each point move the line in the negative direction of the gradient. At the new point. Calculate the new distance from the two node you did not move. If it increased or did not change move the node back and move another node. This will not ensure the fastest route but can significanly cut down the time.

I dont have any code for the above at the moment. I will be trying to write code for each over the next month. If I finish anything that is reasonable you'll be sure to see a post.

:)

[Brykovian]

Originally posted by kedaman
i found GSL templates on the gameai.com you mentioned, looks very good

Kedaman ... what does "GSL" stand for again? {Bryk=too lazy to click over to GameAI and go searching for it:rolleyes: }

-Bryk

[kedaman]

Graph Search Library

[Jotaf98]

Nice avatar + new signature, keda! :)

Illuminator, those ideas seem very cool - but you don't need to make a whole game just to test them (it's probably not gonna take as much as a month) ;)