This Weeks Question: Make an actor find best route using A.I. to destination?

StormyStudio

Stormy Studios question of the week...

SIMPLE ARTIFICIAL INTELLIGENCE

Ok, not yet done any work on this yet but thought I'd throw it out there as a point of discussion.

If you have an actor (lets call him BOB) that is moving to your given destination. (game.destination_X and game.destination_Y)

But on its route it collides with a wall.

How would you tell the actor to rotate and try going along the wall in the best direction until it finds a gap and is carried on towards its given destination....

Quick ideas:
Make game attributes
game.destination_X
game.destination_Y
game.Bob_wall
game.Bob_angle_to_destination
game.Bob_wall_angle

Bob_angle_to_destination is the angle to the destination at any time. (Worked out already).
•••• See here for more details on rotating to angle of destination: Be an Angel fix my angle: http://gamesalad.com/forums/topic.php?id=28229

if BOB hits wall change attribute game.BOB_Wall to 1

if game.BOB_Wall = 1
Change Attribute game.Bob_wall_angle to game.Bob_angle_to_destination

if game.Bob_wall_angle is above a certain angle move and rotate BOB left, or right, or up or down. If the angle is exactly straight at the wall e.g. 90 degrees... the character moves in a figure of eight until it decides on a direction. (I think you could use sin or cos to achieve that with one tidy rule).

If BOB is no longer colliding with Wall rotate bob back to game.Bob_angle_to_destination and move to game.destination_X and game.destination_Y.

Think that sort of works...yet to try it out..

WHATS IT FOR
Not actually sure if I want this for my current project or not but I like the idea maybe for a different game to be able to let the user tell an actor where they want it to go and know that it will eventually get there. Or to create a robot that has to solve a maze...perhaps the user designs the maze ...I don't know just ideas at the moment...

Please discuss... and enjoy...

Cheers

Jon
http://www.stormystudio.com

RThurman

Stormy -- you sure have interesting questions!

But I think you already answered this one.

Another AI technique would be to have BOB follow the maze by always keeping its 'right' side to the walls. (For highly structured mazes.)

Another really fun technique would be to mimic the way the bacterium e.coli move. They swim as straight as they can, then 'tumble' randomly whenever the scent of their food seems to start diminishing. It is an amazingly efficient way to 'blindly' swim to a target.

StormyStudio

...yeah maybe my idea will work...I'll test it later.

but any other different methods for giving a character AI could be good for discussion.

• How to make a character run away from an actor and not get stuck in a corner?

• How to make an actor know to try and dodge bullets? (but not always manage it).

old_kipper

evasion from cornered is one of the hardest things to do. You can use way points projected into 'free' space and then try to achieve them dependant on rules. Or try and build some form of awareness of an escape route, a directive not to get pinned in, or a slipper soap behaviour, or a combination of any/all.

Dodging is less of a problem, but it presumes awareness of incoming.After that its positional movement with rules.

all cool stuff

RThurman

The idea of evasion while being cornered would be fun to work out! I can think of five different techniques to deal with evasion from corner:
1. Like a grasshopper (random jumps -- lots of bumping back into corner and not very efficient)
2. Like a frog (jumps 180 degrees away from enemy -- but often keeps hitting walls.)
3. Like a fox (turns left, then turns right, then turns around and chooses widest opening to slip by)
4. Like a person (turns around and says "No thanks -- not interested" to the salesperson.)
5. Like a lion (turns around and say to itself "ummm... looks like dinner!".)

LumpApps

You forgot
6. like my wife (reminds you of what you told her on march 10 2002

@stormy Did you find the formula on how to make a figure 8?
I am close and have an actor make very nice movements like a floweresk shape and al sorts of strange curves but after a couple of hours I decided it was time for a break.

Will try again tomorrow.

GamersRejoice

I was thinking about invisible way points also. So based on where they are and their current objective they could select the most direct path or the longest path.

InLikeFlynn

You could also give that actor it's own set of invisible walls that let the player pass, but wont let your AI go down areas with no escape.
As far as maze solving behavior, have you thought about sending out invisible simulators to test the quickest path? You could try sending out 5 or 6 who move at a much faster speed and each have their own algorithm. Maybe one of the just pushes in the direction of the exit, while others try the safe routes like always turn right and left. Then the 'winner' could send back directions.

LumpApps

Eureka!

Figure 8 formula:
in an actor ad 2 constrain attributes:
self.position.x = game.centerposx +( game.radius *2*cos( game.anglecenter ))
self.position.y = game.centerposy +( game.radius *sin(2* game.anglecenter ))

Where
game.centerposx and game.centerposy is the position on screen where center of the 8 will be (could be the init position x and y of the actor.

game.radius is the 'radius' of the 8

game.anglecenter is a value interpolating from 0 to 360. This could also be constrained the angle of a second rotating actor but then you will have to use a modulus to keep the values in between 0 and 360.

old_kipper

LudwigHeijden said:
Eureka!

Yippie!

p.s. did you manage to post your demo of the rotationally constrained variable offset actor yet? I up to something that it would be very useful for...

cheers kipper

LumpApps

Uhm, the swinging motion you mean?
No, not used that yet.

RThurman

LudwigHeijden said:
Eureka!

Figure 8 formula:
in an actor ad 2 constrain attributes:
self.position.x = game.centerposx +( game.radius *2*cos( game.anglecenter ))
self.position.y = game.centerposy +( game.radius *sin(2* game.anglecenter ))
.
.
.

So cool! I'm gonna try this today!

RThurman

old_kipper said:

p.s. did you manage to post your demo of the rotationally constrained variable offset actor yet? I up to something that it would be very useful for...

cheers kipper

If all works well, there should be an image of the rules for rotating an actor above this. (This is my first foray into image imbedding.)

These rules have the 'head' pointing at the mouse. But it also will have the 'tail' point at the mouse if the tail is closer. (Like Ludwig's crab's want to do.)

ORBZ

Pathing solution:

I did a little research into AI pathing last year. My conclusion is that GS doesn't really provide the best tools for the job. A* is out due to no arrays.

But, a simple way to do pathing around obstacles is to simply use the acceleration behavior. Eventually your object will "bounce" its way through the cracks towards its target.

It's the opposite of clever AI, but it is low complexity and low CPU and does create a realistic "BOT" that moves towards its goal and avoids obstacles. The key is to have an invisible collision actor that is larger than the visible actor. It bounces off the walls, but to the player it looks like the bot is avoiding the walls intelligently, when in fact it's just blindly fumbling around in the dark. ILLUSION

ORBZ

Also, the 2nd best solution for the pathing question was to use two sensor actors constrained to the nose of the bot. I placed the sensors on the front of the bot and if the left sensor was triggered the bot turned right, if the right sensor was triggered the bot turned left.

That worked ok, but wasn't perfect. The best solution was just bumping around while accelerating towards target. Ya, i was surprised too. Physics > AI

ORBZ

Hmm... I should batch up my AI templates and make them available.

I have like 20 of them.

RThurman

LudwigHeijden said:
Eureka!

Figure 8 formula:
in an actor ad 2 constrain attributes:
self.position.x = game.centerposx +( game.radius *2*cos( game.anglecenter ))
self.position.y = game.centerposy +( game.radius *sin(2* game.anglecenter ))

Where
game.centerposx and game.centerposy is the position on screen where center of the 8 will be (could be the init position x and y of the actor.

game.radius is the 'radius' of the 8

game.anglecenter is a value interpolating from 0 to 360. This could also be constrained the angle of a second rotating actor but then you will have to use a modulus to keep the values in between 0 and 360.

Ludwig,

Your solution works like a charm!

You can also make the object 'point' in the direction of movement by using gold old:
Constrain Attribute: self.Rotation To:vectorToAngle( self.oldX - self.Position.X , self.oldY - self.Position.Y )

You also would need to add two attributes -- oldX and oldY -- to the actor. Then place their constrain behaviors in the mix as well:
Constrain Attribute: oldX To: self.Position.X
Constrain Attribute: oldY To: self.Position.Y

Then you can have a car or other vehicle racing around in a figure 8.

RThurman

ORBZ said:
Physics > AI

That's a great quote! I think I'm gonna make a bumper sticker out of that.

MoneyMaker100

ORBZ...

il be in for that. I have been trying to figure out some basic AI for weeks now. GS just doesn't do it well. Do you have any demos you could share?

RThurman

old_kipper said:
p.s. did you manage to post your demo of the rotationally constrained variable offset actor yet? I up to something that it would be very useful for...

cheers kipper

I just realized that I previously posted a completely different answer to this question. I think what kipper is asking about is making an object swing like a pendulum. Following is an image of the behaviors needed to do this. To give credit where its is most definitely due, this is based upon firemaplegame's swinging/hanging demo. I have just tried to get it into the most simple form I can think of. In this setup, you will need three attributes (which can be seen in the attribute box).



Hope this helps.