Recent Updates

[Jim Sachs]

I don't know how to even boil the problem down to specific questions. A fish is swimming happily along, and suddenly finds itself within an object. Well, it's already too late - there has been a collision. But even then, how to get out of the predicament? Does it back up? What if there is now another fish behind it? And a fish behind that one?

At the moment, I'm using a terrain-height map to watch for collisions with the environment, but this scheme is fairly easy to fool, expecially if a fish is travelling back-to-front.

[feldon34]

Collision Avoidance means that the fish choose paths that won't even take them anywhere near another fish. Imagine if you could use a pen and draw flight paths in 3D through the tank, and before you draw each flight path, you look at all the others first to make sure yours won't overlap. Let's say each flight path is viable for 5-10 seconds. So you keep evaluating new flight paths as the old ones expire.

Yes, it will require Calculus.

Computers have 5 GHz of CPU now.

[Nicki]

The program still has to be able to run on the older more modest machines though , so it can't become too CPU intensive . Although I suppose there will have to be a reasonable hardware requirement - something like 2GHz processor , 128MB of video memory , 512MB of system memory , and MA 2.6 is still a very nice program for those who can't make those requirements .

This is only my 2 cents , but I can live with the odd collision if it means more interesting fish .

[Jim Sachs]

Computers may be 5 GHZ now, but my 60-year-old brain is only 1 MHZ, and diminishing rapidly. As far as Calculus goes, even Einstien admitted that he couldn't have invented it if Newton hadn't already.

[flipper]

Sorry for the long post. I just want to make sure that Jim understands how simple this can be.

My technique doesn't require calculus, per se. And it's not an A* path finding or any other advanced math-based AI approach either. It is based on calculus, but you don't really see that, nor do you need to know any. It's mostly data driven and was born out of 10 years of working with experts in the area of computer simulation modeling of real world physical phenomena.

It's based on random sampling out of probability data sets which can be as simple as 2 2D data points.

It does require some simple 3D math in order to determine if any object needs to be avoided. But it really is stupidly simple because I'm stupidly simple and I don't have good math skills to boot.

It also doesn't take up much of any cpu because it's so simple.

The trick to making it work is tweaking the data. That's why I thought Jim might be interested in the approach, since it falls within the normal things that a modeller is familiar with - tweaking data points over and over until you're satisfied with the results.

As an example, say it's time to change the horizontal direction of a fish. A typical approach to accomplish this would be to generate a random number between 0 and 1 and multiply that by 2 pi to get the new direction of travel. In my approach, that's still done, but you constrain the calculation by giving it a high and low boundary specified by variables. Under normal conditions those variable's values are 0 and 2 pi. But the collision avoidance routine can change the variable's values, forcing the fish in the direction it wants the fish to swim in order to avoid the objects the fish is swimming towards.

An example of collision avoidance would be if the fish is swimming fast towards a tank boundary. The collision avoidance routine "sees this" (simple distance and dot product calculations along with a velocity check) and modifies the fish's direction and acceleration boundary sampling variables so that it starts to "want" to slow down and/or turn.

The "sees this" part also uses the idea of constraint-based sampling, it would just (typically) use more than high and low constraints. For example, say you want a fish to behave normally until it's within 3 seconds of colliding with something. That would be one data point. Then say that if it's within 2 seconds of colliding with something you want it to start to slow down some. That's another data point. Etc, down to the last data point that says that the fish must almost stop if it's within a quarter second of colliding with something.

Go through this same "what-if" scenario to come up with a set of data points for forcing turns and you have what you need as a good starting point for collision avoidance that by its very nature almost never allows true collisions.

Now, extend this basic idea into up/down direction, bouyancy, acceleration, forward speed, turning speed, proximity to other fish, proximity to static objects, proximity to other fish that "scare" a given fish, or are food fish for a given fish, etc. Any behaviour of a fish that you wish to control can be modeled using this technique. Using the same simple math and sampling routines and a little as 2 variables per behaviour. All you need to do is come up with the data driving the behaviour.

[Jim Sachs]

That's pretty much exactly the scheme I've always used for tank boundaries, and it worked great for previous versions. The problem with MA3 is determining what's "inside" or "outside" of objects in a very complex 3D environment. The fish will be able to peck at the coral, which means they need to know exactly where the boundary of the object is.

As I look around my desk, I see a similar situation - a mouse, keyboard, speakers, stacks of papers, a desk lamp. I can reach out and touch the lamp shade, and I can see when my finger is about to make contact, but I wouldn't have any idea how to write an algorithm to do that.

[Rick Simon]

Originally posted by Jim Sachs:

As I look around my desk, I see a similar situation - a mouse, keyboard, speakers, stacks of papers, a desk lamp. I can reach out and touch the lamp shade, and I can see when my finger is about to make contact, but I wouldn't have any idea how to write an algorithm to do that.  

I don't do 3d modeling and I'm not familiar with the process so this may be way out in left field and of no use whatsoever, but can you wrap the fish in a transparent "conformal bubble" and detect collisions between that "bubble" and the environment? If the bubble extends outwards xx pixels from the body of the fish, you could use that collision detection as a trigger that the inner (visible) fish is "about to make contact". That might give you enough time to call the appropriate sub-routines to smoothly handle the situation without having the fish appear to actually collide.

[Jim Sachs]

Yes, that's a bounding sphere, and is actually much easier than it sounds. There's a DirectX function for measuring the distance between the center of your object and any point in space. The problem is figuring out which points in space to measure to.

[Nicki]

Rick , I think that is pretty much how Alan does it at DA , which works very well for most the of the fish that are in the program right now . The dwarf gouramis though are quite flat and can pass through rocks and each other , but not so often that it ruins the realism . They are able to peck at the rocks/wood and shoal nicely together . He's trying to find models that work with long finned/tall flat fish like Bettas , Angels and Discus - although I'm really wanting Corydoras catfish . Also I think he wants to introduce different behaviour models for each species because although the fish look very natural now to the untrained eye , they all act the same .

Calculus , the very thought of it makes my toenails curl . It was a necessary evil to get my advanced high school diploma and thereafter my BSc . Glad to have forgotten nearly all of it now . What really craws though is that we would pester our teachers about what good it was going to do us in our everyday lives , and they said we would use it all the time . Sure , we said mockingly , and then we find out it's a good thing to know if you are trying to create a hyper realistic virtual marine aquarium . They might yet be right - what a jip !

[Dale]

Are the more-realistic fish models (how individuals look and behave as individuals), directly related to the "collision avoidance" problem? Or are those essentially-separate factors?

[Jim Sachs]

They are related in that the new fish will use natural swimming movements to get out of sticky situations, instead of just "repelling".

[Dale]

Originally posted by Dale:

Are the more-realistic fish models (how individuals look and behave as individuals), directly related to the "collision avoidance" problem? Or are those essentially-separate factors?  

Originally posted by Jim Sachs:

They are related in that the new fish will use natural swimming movements to get out of sticky situations, instead of just "repelling".  

Let me ask that a different way: would it not be possible to use the more-realistic fish models, with the current-production "repelling" algorithm?

[Not suggesting that you would want to do that as an interim measure]

[Jim Sachs]

It's possible.

[Nicki]

You'll get there Jim . As we say in Canada , keep your stick on the ice ! ( Basically it means take care , look after yourself etc ) .

[jleslie]

I'd be tempted to do it this way:
(1) Give each fish a destination it's going to (might include staying still).
(2) Plot a path to that destination using its desired route (straight, meandering, etc).
(3) Use a simple version of the tank, with low-polygon geometry and fish to run what-ifs for 2-3 time advance periods to look for collisions. (All done by DX.)
(4) If a collision is detected consider another route for one or both of the fish.
(5) Perhaps use a higher resolution model for +1 frame time movement.
John

[flipper]

Originally posted by Jim Sachs:

That's pretty much exactly the scheme I've always used for tank boundaries, and it worked great for previous versions. The problem with MA3 is determining what's "inside" or "outside" of objects in a very complex 3D environment. The fish will be able to peck at the coral, which means they need to know exactly where the boundary of the object is.

As I look around my desk, I see a similar situation - a mouse, keyboard, speakers, stacks of papers, a desk lamp. I can reach out and touch the lamp shade, and I can see when my finger is about to make contact, but I wouldn't have any idea how to write an algorithm to do that.  

Instead of a heightmap, I use small bounding boxes by subdividing each non-fish object into a 3D grid along each world axis. Think of a bunch a sugar cubes stacked and arranged to encompass your model's interior. You can also combine boxes that are "next" to each other as long as the result is still a box. You can generate these at runtime, using each non-fish model's vertex data, or you can pre-calc and store them ala your heightmap, or you can use your modeller to create a separate "collision" mesh for each non-fish model, load that model into system memory, and then use that vertex and face data. Just remember to keep the vertices aligned so that they form "axis aligned bounding boxes." (I'm sure you've seen that term before.)

Then, for the "close enough to influence" objects, iterate through each of that object's sub-boxes, and find the distance between the fish's world geometric center point and that box's closest surface, edge, or corner, using a "point to box" routine.

The "point to box" routine is pretty straight-forward. It compares the point against the box's min and max boundaries for each world axis, developing a bit mask that represents which of the possible 27 sub-cubes the point is in with respect to the box's interior region.

To generate the bitmask, start it out as 0, which represents the box's interior sub-cube. If the fish's x value is less than the box's min x value, add 1 to the bitmask. If the fish's x value is greater than the box's max x value, add 2 to the bitmask. Use 4 and 8 for the y axis and 16 and 32 for the z axis. This gives you the 27 possible values of 0, 1, 2, 4, 5, 6, 8, 9, 10, 16, 17, 18, 20, 21, 22, 24, 25, 26, 32, 33, 34, 36, 37, 38, 40, 41, and 42 for the bitmask. If you work through an example in 2D you should see how the numbering scheme works.

Then work out what's closer for each given sub-cube that the fish may be in. It will either be a box corner, edge, or side, or the fish is within the box, in which case you can consider the "point to box" distance to be 0.

There are 8 corners, 12 edges, and 6 sides to consider. For bitmasks 21, 22, 25, 26, 37, 38, 41, and 42, the corners are closest. For example, bitmask 21 represents a point that is left, below, and in front of the box. For bitmasks 5, 6, 9, 10, 17, 18, 20, 24, 33, 34, 36, and 40, the edges are closest. For example, bitmask 5 represents a point that is left and below the box but within its front/back boundary. For the other bitmasks (besides 0), the sides are closest. For example, bitmask 1 represents a point that is left of the box but within its up/down and front/back boundaries. (I used lefthandedness-speak here.)

So all that's left is to do a 3D "point to point" calculation using the fish's position and the box's closest point as specified by the bitmask. For closest corner calculations, the box's closest corner is the box's closest point. For closest edge calculations, you get the box's closest point by using its 2 axis values for the axes that don't "bound" the fish, along with the fish's axis value for the axis that does "bound" the fish. And for closest side calculations, you get the box's closest point by using its 2 axis values for the axes that do "bound" the fish, along with the fish's axis value for the axis that doesn't "bound" the fish.

Does that make enough sense to give it a try? If not I'm sure there's code on the web that uses the same idea. Or I'll post the code I use if you want.

[harris]

Through the years I have enjoyed many first-person-shooter games. It started way back in 1987 with "missile command" (I think that was it's name) and for the last few years I've enjoyed using Marine Aquarium and following its development starting with version .99f.

One thing that I never gave much thought to until reading Jim's, Flipper's, and others' posts is how complicated it is to develop games and software like the "Marine Aquarium Simulator" aka Marine Aquarium 3. I would like to say to Jim although you have hit a rough spot in the road, don't let it get you down. It looks like you have many fans here that are very knowledgeable and are eager to help with thought provoking suggestions.

Hang in there Jim.

[Jim Sachs]

Thanks for the encouraging words.