I'm working on designing a space strategy game(still deciding between turn based and rts... i'm thinking turn based with real time battles). Anyhow, one of my key decisions at the moment is to go 2d or 3d. One system I want desperately to include is a border system. Basically after you've explored so much unclaimed space you're able to declare it to be under your ownership until someone tries to take it. The problem is this: I want to do the game in 3d, because so far I haven't thought of any other major difficulties in doing it 3d as opposed to 2d other than the border system. If done as a 2d game I'd be using a hexagon based system that would be all but invisible to the player. However with 3d I'm unable to figure out how I would draw the border. The way I want the border to look is basically a growing line or field around friendly territories (or enemy) whenever the player pushes a button to turn it on (not on all the time mind you). I've figured out how to calculate the points involved, but I haven't yet figured out how to connect them. Obviously I can look at it and say "start here and go here", but I haven't figured out a valid algorithm to connect the shapes. Here's a two dimensional example. The X's represent points around the far left star I would want to establish a border around. If I could figure out the principles behind drawing the shape in two dimensions I can't see the principles being much more difficult in three dimensions. I've practically beat my head against the wall trying to come up with an algorithm to figure out what order to connect the points in. After I figured out the order I assume I could string together some triangle strips to actually draw the thing (but I'm not 100% on that either). I would gladly accept someone else's infinite wisdom on the most efficient way to do this. Thanks all.

Sounds like you need to calculate the bounding hull from a bunch of points. While thats not too hard in 2d, its really quite tricky to do in 3d. Perhaps QHull could save you some time.

To connect the points in 2D, I would determine the Z-value of the cross product from an arbitrary starting point to each of the other points, then loop through them in order (starting and ending with the selected starting point).

Of course, that only works in two dimensions. It may be possible to use a similar method with higher-dimensional products, but I don't know how you would get polygons out of that.

-rc

OrangyTang
-Thanks for a fast response! I will look into QHull. Depending on speed it seems like it's something I could use. Otherwise, I may have to try other alternatives to achieve the end results I want.

RabidCow
-Also thanks for a fast response. Just for my own enlightenment I would like to understand the explanation you have given me. Would you mind giving a detailed example?

Thanks again!

Unfortunately, if I go with a 3dimensional solution I'll have more than one plane.

I also had another thought. How taxing are the spherical shapes that can be automatically generated in directx on the processor? My thought is simply to generate a sphere of influence around around systems and space stations rather than worrying about complex shapes.

The trouble I can see is if something interupted the sphere. For instance if I had a spherical boundry of control around a sytem, but a neighboring system became controlled by an enemy empire then the boundry would be "squashed" on one side only. In that situation I would need a way to slice the sphere or flatten it. Keep in mind this doesn't have to be done in real time if I'm doing a turn based system. Hrm :/

Thanks again for all the help.

noisecrime -
I love both of your ideas. I had briefly considered projecting it as a 2d image over the current 3d display, but i'm not sure how clearly you would be able to see the border. I would have to experiment and find out. Of course, I still need to figure out how to connect 2d points (which I haven't quite got a grasp on yet).

The meatball idea was kind of what I was getting at in my previous post talking about the spheres around each body or station. As seen above the trouble is if I have something that would restrict the border on one side. An example below.



I would need some easy way to deform the shapes. Again thank you everyone for helping.

Ooo, metaballs, now theres a good idea. :) A 2D only solution wouldn't be much good I think, since it only provides a visual indication, you wouldn't actually be able to use it for gameplay stuff as that would require finding the proper 3d solution.

Theres a good article on metaballs on gamasutra, which covers calculation and rendering. Or you could improvise and project your metaballs' fields onto your viewing plane and solve it in 2d as well (and solve the actual equations at a point for gameplay stuff).

HAHAHAHAHAHA
I can't believe it. I totally read that as MEAT balls instead of metaballs. I just assumed it was analagous. I'll check out the article. Thanks everyone.

Edit:
I haven't found the article on gamasutra yet, but I have found some information on metaballs. First reaction: O_o

I may have to crack a mathbook or two on this one. I'll keep working at it though. Once again... thanks.

Edit again:
Read the gamasutra article. Once again O_o
Anyway I do think this is a very viable solution to my problem... IF I can understand it and apply it practically. I want to get a working rendering example before I decide on it. I get the feeling it's going to be hard to find too many code examples.

[Edited by - Jackbunny on September 3, 2004 9:59:10 PM]