Hello everyone,

I am working on writing a game in Flash, and I am having a bit of trouble
figuring out how to work the AI. Basically, there is a non-player character
that needs to know how to move towards the player's character; however, the
environment has boundaries and things that cannot be moved through, and the
boundaries are of an irregular shape.

Here is my crude represetnation of how the situation looks:

(note the .'s represent blank spaces)

----------------------------------------
|....................................................|
|....................................................|
|.......x...........................................|
--------------................--------------
..................|...............|
..................|...............|
..................|...............|
..................|...............|
..................|...............|
..................|...............|
--------------................--------------
|....................................................|
|............o......................................|
|................................................... |
----------------------------------------


Basically, the NPC (marked with the 'x') needs to get to the player (marked
with the 'o') without going through any walls, and by only using the actions,
turn left, turn right, or move forward. It needs to do it in the shortest
possible way, so that it doesn't look crazy to the player of the game.

I am a computer science major in college, and I am familiar with the
shortest-path algorithm, however I don't know how to find out the shortest path
when you don't have nodes. (And no, hard-coding it is not an option, because
1) the player will be moving around, and 2) I need to be able to re-use the
AI on different levels).

Thanks very much to anyone who is able to provide help on this very tricky
problem!

--Philip

The "barriers" are really just places that the characters can't walk, at least
in this case. (By which I mean, they can see through them; it's just that they
can't walk there because they would fall to their deaths.) There won't be any
instances in this part of the game where they will need to avoid things,
although grenades may be introduced later that would cause them to want to move
away. At this point the characters won't be smart enough to try to dodge the
bullets, which would probably be too fast to dodge anyway (although they are
greatly slowed down for the purposes of this game).

Ohh, I think I may see what you're getting at. Were you going to suggest that
the characters just try to try to maximize the decrease in the differences
between the x- and y-cooridnates of the x and the o? So basically they just
keep checking different rotation positions until they find one that makes them
have possible moves that get them closer to the player as much as possible?
(In other words, they don't care about finding an exact route, they just try to
get as close as possible.) That seems so simple, I'm not sure myself if that
would work...would it? (I'm assuming you know, haha). Or were you going to
suggest something completely different?

If there comes a point where it becomes necessary to avoid certain things, I
will just add that check in as a conditional before the go-closer-to-the-player
routine, or whatever I decide to call it. So basically it would just abandon
the main routine if there was something that needed to be avoided.

But yeah the short answer to your question is: they will be all-seeing in
every level of the game. Just out of curiosity though, how would the answer
change if they were not?

Thanks very much.

--Philip

The "barriers" are really just places that the characters can't walk, at least
in this case. (By which I mean, they can see through them; it's just that they
can't walk there because they would fall to their deaths.) There won't be any
instances in this part of the game where they will need to avoid things,
although grenades may be introduced later that would cause them to want to move
away. At this point the characters won't be smart enough to try to dodge the
bullets, which would probably too fast to dodge anyway (although they are
greatly slowed down for the purposes of this game).

Ohh, I think I may see what you're getting at. Were you going to suggest that
the characters just try to try to maximize the decrease in the differences
between the x- and y-cooridnates of the x and the o?

if x "sees" or "knows" the entire map (_level means something else in flash), x
can chart their handful of plausible courses to o. if there are no trick maps
with blind alleys etc they can move directly towards o unless there's a
barrier. if there's a barrier they have 2 plausible options, left or right.
each leads to a plausible path. with each path if they can move towards o, do
so. if x cannot towards o, move left or right same as their previous direction
when this barrier was encountered. etc.

everytime they move towards o and then hit an object 2 plausible paths will
result. etc until there are collection of plausible paths. x will pick a path
that contains a minimum of steps. they take the first step in that path.
repeat with each turn using updated information on o's location.

if x was blind, he would pick a plausible path without calculating all paths
(and picking the one with a minimum of steps). there wouldn't be much ai for x
to employ. he would simply stick to a direction when a barrier is encountered
until he's trapped or he can close the distance to o. if he's trapped, he
moves in the opposite direction, if he can close the distance, he does so.

can x "see" the level so he can calculate the shortest route before starting?
will a level contain blind alleys or other traps that may require x to move
away from o (temporarily) in order to reach o eventually?

Hey everyone,

Haha, whoa, lotta replies.

Okay, I will look at pathfinding and A*...not sure what those are...but I'll
look...I do know a little bit about shortest-path algorithms, but honestly I've
never covered ones that don't involve graphs with nodes. I will look though,
probably tomorrow morning.

Kglad...they will all be vertical or horizontal paths. I'm not sure that I
understood everything that you said, some of the wording was not clear to me.
Do you think you could try to re-explain it in just like, simple step-by-step
format? If not I understand, haha; I don't mean to rob you of too much of your
time. I was particularly confused by the use of the word plausible...I know
what it means usually, haha, but does it mean possible, probable,
definitely-working, or something else in this case?

Is there a website that explains all this? Oh right, and I will search for
pathfinding when I get a chance.

Abeall...it's an art-based game, I don't have tiles and there are 72 different
directions that can be travelled in by any of the characters.

Sorry that I am not understanding what you guys are saying right away...maybe
if I sleep on this and wake up tomorrow it will all suddenly make sense, you
never know haha.

Alright, thanks once again everyone...good night!

--Philip

If it's art based you're in for quite a task. A* is designed for tile based.
Kglad's suggested solution appears to be something very tricky, where the AI
tries to move based on smarts. I've tried this(when an AI runs into a wall, he
turns and tries to go around) but I didn't get anywhere. Hope you have better
luck.

You can still use a node based system, however. I've done this personally in
Flash, although my algorithms for finding the shortest path were probably not
entirally sound(though they worked). All you really have to do is, when you
design your map, place nodes in logical places. Then link them together, either
by hand or some sort of automated system(which is what I used) which simply
loops sthrough all nodes on the start, and links them to any other nodes it has
line of sight to.

Then from there, use the good old Dijkstra's algorithm. My algorithms were
completely home concocted(for fun more than anything, in fact I didn't know
about any standard pathfinding algorithms at the time, but there are lots out
there) so you'd be better off working from the master's.

Good luck.

plausible path: if a vertical barrier is encountered either go up repeatedly
until a path towards x is available or go down repeatedly until a path towards
x is available. one of those two are the two best options given that a
vertical barrier is encountered and there are no blind alleys.

an implausible path would be to consider going up a number of steps, then down
some number of steps, then up some steps and then down some steps etc. that is
not going to be an optimal path and constitutes an implausible optimal path
choice.

the only plausible candidates for a minimal path is up repeatedly or down
repeatedly until a path is available to x or until a blind corner is reached.

likewise with a horizontal barrier.

just to be clear: a blind alley:

| |
| | <-- two unbroken vertical barriers
|______|

another blind alley:

_________________
| <-- unbroken vertical barrier
|
|___________________

Kglad,

Thanks very much for the help...I'm not sure if I understand everything
correctly though. Also, I think I may have explained something incorrectly;
the AI can move in pretty much ANY direction, not just up/down/left/right (well
technically, they can move in 72 directions because they can change direction
by 5 degrees). So the NPC would have more than just left and right to choose
from when it hits a barrier. When I said that two of the options for moving
were left and right, what I meant was that they could turn either 5 degrees to
the left or 5 degrees to the right, while standing in the same place.

Also, I have one other concern. What happens if the character is in a
position where he is directly vertically above (i.e., y-coordinate-wise) the
player, and thus moving left or right will always take him farther from the
player? How would he decide which way to go then?

Thanks again...sorry if I am not understanding everything you're saying
completely, I'm a bit slow when it comes to understanding spatial concepts,
haha.

--Philip

will barriers always be vertical or horizontal? if so, then it doesn't add any
complications to allow x to turn 5N degrees.

if barriers can be at any 5N degree angle then that would add a minor
complication, but one easily handled by flash and the path decision logic i
sketched above.

there's no problem with x about to encounter a barrier if he continues in a
straight line towards o. the ai i outlined does not try to make each step one
that will minimize the distance to o. that would be doomed to failure.

the ai i sketched would determine all reasonable paths to o and then select
one that contains a minimum number of steps. a step is a unit move. i'm not
sure what your units will be but that's not relevent to the problem.

SIMphilip -