got a good algorithm for radar system?

Why not computing the distance between your objects and then if it fits in your radar range adds it in your radar buffer ?

I think if you use an array of pointer it would be faster than a linked list, but you have to find the good size for it... I think something like this would do the trick :

// Global variable
Object Radar[MAX_NUMBER_OF_OBJECT];

//
// Find all objects in that range and return the number of found objects
//
int FindInRadarRange(float range)
{
int position=0;

// Clear the array very fast
memset(&Radar, 0, MAX_NUMBER_OF_OBJECT);

// Find all object in the range and add them in the array
if (object distance is shorter than range)
{
Radar[position++] = Object_Position;
}

return position;
}

Good luck

- Iliak -

If you are calculating the distance between your objects make sure you use the squared distance

e.g (Squared DIstance From Object) <= (Squared Max Radar Distance)

If you dont, you''ll be doing square roots on all the objects in your world (or sector or whatever), and that''ll kill your frame rate, which no-one wants to see

Using a static array maynot be your best option either, for the usual reason that its limited in size (so you''ll either run out of space or have one thats way too big). Dynamic arrays, or linklists/vectors would be more appropriate.

There are plenty of alternatives but one I thought might be suitable is to use some sort of space partitioning.

I know you said you wanted a continuous world but you can implement one in sections and then dynamically load them, just like in iso/tile based games, as the player moves/flies. Anyway if you split the world up into discrete sections you then only have to test the sections within radar range of the player, skipping all the others. This could be impletented using something like a quad tree or perhaps only have certain number of sections loaded at any one time. This approach would be memory friendly and loading friendly as you could stream all the data off the hard drive as the the player moved from section to section. Another benifit is for in maintaining the universe state, because there is only so much of the universe loaded at any one time, you don''t have to try and update the entire universe each tick.

Have you listened words Spanish moss algorithm?

hm.. the first thought would probably be octrees, the next one, as space is such an empty thing might be loose octrees. but as a quick and dirty method you shouldnt run into problems doing it per object for a few hundred objects (at least having 500 ships firing at each other at 5 shots per second and doing the collision tests didnt hurt that much.. the ai did though ,-) )

btw. frustum culling and your radar are pretty much the same (as long as your cockpit and camera position are the same). you got your ships position and orientation, if you just store its transformation matrix you got front,right,up and position vectors, getting their positions relative to your ships is a matter of dir=object.position-player.position and x=dot(dir, player.right), y=dot(dir, player.up) etc.. thats the part you will need for both.

having the relativ position and using the simple fact that your frustum planes a simple lines from above or the side you need the right factor (fy=tan(fov/2) and fx=aspect*fy), multiply the z-coordinate of the relative position with fx or fy to get the limits for x and y (xlim, ylim). if x is between -xlim and xlim etc. its inside the view frustum.

Actually most efficient way would be: do deltas.

if /< c%10!=0 /> create delta();
//else you should count all

So you'd just count ships that left radar range and ships that entered in and store results with previous iteration. Then just count for each ship in the array if it was detected or not.
As I said Spanish moss would give you an idea for preliminary search, or you could just use Trienco's ideas.
Do you have ready to use data structure for close ships, or are you at "early" stage of designing 3D engine?

[edited by - Raghar on October 17, 2003 8:03:21 PM]

I already have a single player demo of space ships flying and fighting. But there''s no radar.

I think that octree space partitioning is the best way to go. However, it''s not the easiest thing to implement. Octrees usually deal with static objects, not dynamic onces, like space ships. What I want now is suggestions on how to implement this sucker. Has anyone done it?

the one thing that always made my head hurt: space is infinite but your highest octree node cant have infinite size, so you''d either have to add single trees next to each other (killing trees and branches that are completely empty) or if you have something like a combat zone use a tree for this and just consider everything outside the tree as one (as there shouldnt be many). and of course keep the size of the leaves big enough, no need to let them grow small enough to only hold single ships.

another problem might be limits and precision of floats (the natural limit for the size of your space if you dont do anything about it ,-) )

Octrees are definitely your best bet. You really already should be using an Octree for rendering in a space game.

what about an N-tree, reading through an aticle at Gamasutra, it suggested that an n-tree is probably better for game with lots of "open space". Also, as i said earlier an infinite space, or at least a much larger space can be implemented if you split it into quadrants, also it might make editing easier.

As for the radar, how you do it depends on how you partition your space. I''d go with an octree or n-tree, just amke sure you implement it in a way that works well with lots of dynamic objects, could then implement orbiting planets later...