My next programming challenge I have set myself is to simulate
and display (crudely) an 800m race (2 laps of the track).
Suppose you have 8 runners (or horses or whatever) they all have
various attributes, top speed, acceleration, stamina etc...
how would you approach this?
As I see it there are two broad approaches you can take
1) Set the trajectory each runner will take in advance
then just deal with avoiding the other runners and
how fast they are going.
2) Dynamically figure out the trajectory in real time
I am thinking of going with 1) because it seems
a lot simpler. I could take a rough oval around
the track and put some small random deviations
in for each runner.
My next priority is creating
races that are interesting to watch. I
want to avoid just all the runners following
more or less the same route tight to the inside
(which may well be realistic but I'm not too concerned
about that) then running at the same constant
speed until they get tired. On the other hand
if not all the runners stick to the inside they are
at a large disadvantage.
How would you go about it? Any ideas? I'm
just sort of brainstorming seeing what gets
bounced back,
I am programming in C++ by the way, not
too experienced but learning fast.
How Would You Tackle This Simulation?
You could represent the track as a large array of available movement slots something like:
XX111111111111111111111111XX
X10000000000000000000001X
10=====================01
10=====================01
X10000000000000000000001X
XX111111111111111111111111XX
Each spot on your array has a value associated with the movement cost with lower being better so each step of the runner he will choose the quickest route.
You would have to do somethig to prevent them from running in reverse but you get the idea.
If another runner is already in that spot the runner behind him will have to go around at a higher movement cost.
I am sure there are way better ways to do this but just something I thought of.
XX111111111111111111111111XX
X10000000000000000000001X
10=====================01
10=====================01
X10000000000000000000001X
XX111111111111111111111111XX
Each spot on your array has a value associated with the movement cost with lower being better so each step of the runner he will choose the quickest route.
You would have to do somethig to prevent them from running in reverse but you get the idea.
If another runner is already in that spot the runner behind him will have to go around at a higher movement cost.
I am sure there are way better ways to do this but just something I thought of.
Author
Thanks!
I hadn't thought of doing it that way. You also gave me the idea that I
could make some tiles have a better surface. If I put these better tiles closer to
the outside then that solves my problem of everyone choosing
the shorter inside route!
I hadn't thought of doing it that way. You also gave me the idea that I
could make some tiles have a better surface. If I put these better tiles closer to
the outside then that solves my problem of everyone choosing
the shorter inside route!
Personally I would use Steering Behaviors. More details. There is even a C++ library of the algorithms.
For long distances it might make sense to construct the path as a series of nodes, use A* pathfinding to find the shortest path (with movement costs as previously mentioned) and then use the steering behaviors as a way to navigate between the nodes.
In-fact from the A* pathfinding link:
For long distances it might make sense to construct the path as a series of nodes, use A* pathfinding to find the shortest path (with movement costs as previously mentioned) and then use the steering behaviors as a way to navigate between the nodes.
In-fact from the A* pathfinding link:
Steering Behavior for Autonomous Characters: Craig Reynold's work on steering is a bit different from pathfinding, but it can be integrated with pathfinding to make a more complete movement and collision avoidance system.
[/quote]
There is also the notion of Reactive planning. It is possible to combine a Finite State Machine with the above and obtain a lot of interesting and unique behaviors.
Also just for fun there is Boids. Which:
At the time of proposal, Reynold's approach represented a giant step forward compared to the traditional techniques used in computer animation for motion pictures. The first animation created with the model was 1987's (Stanley and Stella in) Breaking the Ice, followed by a feature film debut in Tim Burton's film Batman Returns with computer generated bat swarms and armies of penguins marching through the streets of Gotham City [3].
[/quote]
A neat little javascript simulation of it.
It may very well be complete overkill, but hopefully it is interesting.
Good luck!
Author
Thanks. I didn't really consider steering behaviours because
I thought it was too simple but after reading your post
of course thats exactly the situation you want to learn
these things! I am a little worried it will give all the runners
the same behaviour but I will cross that bridge when I
come to it Thanks again for your time, really useful!
Edit: Reactive planning combined with Finite State Machine
sounds interesting as well, thanks!
I thought it was too simple but after reading your post
of course thats exactly the situation you want to learn
these things! I am a little worried it will give all the runners
the same behaviour but I will cross that bridge when I
come to it
Thanks again for your time, really useful!Edit: Reactive planning combined with Finite State Machine
sounds interesting as well, thanks!
You are welcome.
In regards to the same behaviors, that is why the steering behaviors and/or A* pathfinding alone are not enough. These methods allow a way to somewhat realistic travel between two points, but the decisions used to arrive at which points and the steering behaviors to use are where a FSM could come in handy.
Think of this what: If all runners have the same abilities and travel with the same goal (shortest distance, fastest time, avoiding other runners, etc) then they will all travel in roughly the same way. Even with pseudo-random fluctuations, you will observe patterns and unrealistic behaviors.
The way you get different behaviors is to have different objectives and different properties. Some runners could favor straight lines but not be very good at abrupt changes in direction. Some runners might be good at short bursts of speed but have poor endurance. Some runners might not quite want to win, but to prevent OTHERS from winning. This in turn changes what states that they will be in, and what steering behaviors/paths they will follow.
I have always thought that with multiple agents the movement costs are largely individual to the specific agent. A water tile has a high movement cost to someone in a car, but someone in a boat views water tiles with a much lower movement cost!
I think reading up on the Pacman Ghost AI might be helpful.
In regards to the same behaviors, that is why the steering behaviors and/or A* pathfinding alone are not enough. These methods allow a way to somewhat realistic travel between two points, but the decisions used to arrive at which points and the steering behaviors to use are where a FSM could come in handy.
Think of this what: If all runners have the same abilities and travel with the same goal (shortest distance, fastest time, avoiding other runners, etc) then they will all travel in roughly the same way. Even with pseudo-random fluctuations, you will observe patterns and unrealistic behaviors.
The way you get different behaviors is to have different objectives and different properties. Some runners could favor straight lines but not be very good at abrupt changes in direction. Some runners might be good at short bursts of speed but have poor endurance. Some runners might not quite want to win, but to prevent OTHERS from winning. This in turn changes what states that they will be in, and what steering behaviors/paths they will follow.
I have always thought that with multiple agents the movement costs are largely individual to the specific agent. A water tile has a high movement cost to someone in a car, but someone in a boat views water tiles with a much lower movement cost!
I think reading up on the Pacman Ghost AI might be helpful.
Here's an idea using some "thinking outside the box"...
Create a fixed range from 0-1, in the form a single-precision floating-point integer (type flot); 0 represents the very inside of the track and 1 represents the outside. You could also do this as a texture than changes, in smooth gradient, from black to white. Each entity (runner, horse, car, whatever...doesn't matter) will "seek" a lower number, trying to get closer to the inside and gain the advantage. However, they will check for obstacles in their way (rocks, other entities, whatever) and avoid them. If another entity is directly in front, slowing them down, then they will sacrifice space to the inside to pass on the right. This can be achieved with good performance through a quick radius check which leads to more detailed checks against objects within it (bounding box/sphere, collision hull, actual geometry, etc).
EDIT: Use the texture idea if you have to represent a complex track with varying optimal paths and complex obstacles. If it's just a plain, round, paved track like a NASCAR track then just using a simple float value will work fine.
Create a fixed range from 0-1, in the form a single-precision floating-point integer (type flot); 0 represents the very inside of the track and 1 represents the outside. You could also do this as a texture than changes, in smooth gradient, from black to white. Each entity (runner, horse, car, whatever...doesn't matter) will "seek" a lower number, trying to get closer to the inside and gain the advantage. However, they will check for obstacles in their way (rocks, other entities, whatever) and avoid them. If another entity is directly in front, slowing them down, then they will sacrifice space to the inside to pass on the right. This can be achieved with good performance through a quick radius check which leads to more detailed checks against objects within it (bounding box/sphere, collision hull, actual geometry, etc).
EDIT: Use the texture idea if you have to represent a complex track with varying optimal paths and complex obstacles. If it's just a plain, round, paved track like a NASCAR track then just using a simple float value will work fine.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
