Sign in to follow this  
Three Door Cinema

How Would You Tackle This Simulation?

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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. Edited by yewbie

Share this post


Link to post
Share on other sites
Personally I would use [url="http://www.red3d.com/cwr/steer/"]Steering Behaviors[/url].[url="http://www.shiffman.net/teaching/nature/steering/"] More details[/url]. [url="http://opensteer.sourceforge.net/"]There is even a C++ library of the algorithms[/url].

For long distances it might make sense to construct the path as a series of nodes, use[url="http://www.policyalmanac.org/games/aStarTutorial.htm"] A* pathfinding[/url] 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:

[quote]
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 [url="http://en.wikipedia.org/wiki/Reactive_planning"]Reactive planning[/url]. It is possible to combine a [url="http://en.wikipedia.org/wiki/Finite-state_machine"]Finite State Machine[/url] with the above and obtain a lot of interesting and unique behaviors.

Also just for fun there is [url="http://en.wikipedia.org/wiki/Boids"]Boids[/url]. Which:

[quote]
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]

[url="http://gpolo.github.com/birdflocking/"]A neat little javascript simulation of it.[/url]
It may very well be complete overkill, but hopefully it is interesting [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] .

Good luck! Edited by shadowisadog

Share this post


Link to post
Share on other sites
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 [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] Thanks again for your time, really useful!

Edit: Reactive planning combined with Finite State Machine
sounds interesting as well, thanks! Edited by Three Door Cinema

Share this post


Link to post
Share on other sites
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 [url="http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior"]Pacman Ghost AI[/url] might be helpful.

Share this post


Link to post
Share on other sites
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. Edited by ATC

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this