Return to “Polls”

NPC swarms or Collision physics accuracy?

Hundreds / Thousands of NPC's, very basic collision detection (possibly limited to a radious around the player).
Total votes: 57 (52%)
Dozens / Hundreds of NPC's, very accurate collision detection (system-wide).
Total votes: 53 (48%)
Total votes: 110
Post

What is important to you? Many npc's or accurate collisions?

#1
Of course there is the possibility of a coding miracle by Josh again where we can have both :mrgreen:
But in the risk that it isn't possible, what is your own personal preference?

Would you rather see a massive number of npc's flying around in the system you are in, mining, pirating, trading etc.
Absolute swarms in populated systems (remember, outskirt systems will always see less population, we're talking the core systems here).
But with very basic collision detection, perhaps limited to a radious around the player, resulting in weird situations where an npc perhaps wins a fight it shouldn't have won, by clipping through an asteroid (even if far enough away that the player can't see or notice it).

Or would you rather see very accurate collision detection so that no such "unfair" accidents can occur, even far beyond the sight range of the player.
Even if this means that the npc number in core systems must be dropped substantially lower to keep the framerate up?

Vote, let's see where the majority stands on this issue.
Personally, i'm always a sucker for numbers. The Star Swarm tech demo. The Zerg in Starcraft. The streaks of uncountable space traffic in X Rebirth (perhaps we can get some sort of "visual-only" traffic in the same spirit as in X Rebirth around stations or along popular tradelanes, that dont require ai nor collision detection?). :thumbup:
Post

Re: What is important to you? Many npc's or accurate collisi

#3
Collisions are an interesting one. We could be talking about ship-on-ship collision or shot-to-ship collision as well. When it comes to game logic and programming, these are exactly the same thing.

Unless Josh wants to SPECIFICALLY code for collisions in your sight range vs. non sight range (instead of just out-of-system), we probably won't be able to get this without affecting shooting accuracy.

Not to say it can't be done. Dynamic collision simulation LOD? Yummy. I'd love to see that as a solution.
Image
Early Spring - 1055: Well, I made it to Boatmurdered, and my initial impressions can be set forth in three words: What. The. F*ck.
Post

Re: What is important to you? Many npc's or accurate collisi

#7
I think Josh could probably pull off an optimization miracle and get it to work with hundreds of NPCs and great collision, but thousands is a stretch.

With good LOD it should be possible. Josh already uses "history" LOD to roughly determine some things before they need to be fully rendered. Maybe a similar sort of thing could be used here.
They shall call me, Draglide! The thread killer!
Post

Re: What is important to you? Many npc's or accurate collisi

#12
Cornflakes_91 wrote:
Talvieno wrote:Collisions are hard.
it was more significant with your code snipped and detailed description
Fine, no idea how you saw that in time, but I'll repost it. lol


I'm not sure everybody understands the difficulty in detecting collisions... I see some of you clearly do, so for those who don't:
Spoiler:      SHOW
Collision detection is a very difficult area of what is largely advanced mathematics. In real life, we can simply watch with our eyes to see where something collides. Computers do it entirely with numbers. Try calculating on paper the exact instant an irregular object will collide with another irregular object, to what distance they'll be repelled, at what speed, what momentum they'll lose, and the rotation factor gained from the collision. And show your work. Good luck.

Basically, the only truly simple types of collisions are between regular shapes such as spheres, cubes, and rectangles. Tilting the cubes and rectangles makes things interesting. If you find an ovoid (elongated sphere), again, good luck. It can all be done mathematically, but doing it in a decent amount of time is the challenge. Even worse is the fact that the computer can't easily immediately tell whether the two objects in question are close enough to collide at all, and if you don't optimize, your frame rate will be dragged down exponentially relative to the total item count in the system. Again... good luck. Remember that every measurement of distance has to be done using mathematical roots (square roots, cube roots), and in large quantities, this tends to be an enormous processor sink unless carefully optimized. (read: calculating distances is a lot of math. relatively speaking. It's not like abs(A - B). )

In other words, collisions are hard. The more you optimize the system, the more complex everything is going to become. Josh has a slight advantage in that all his ships are procedurally generated from basic geometric shapes. He also has some very irregular asteroids, too, so you have to keep in mind that that is potentially a very major disadvantage.

The simplest collision detection is done using spheres, and I'm sure you've seen it in some older games. Copying from some of my code...

Code: Select all

for (int i = 0;i<name.size();i++){
	for (int j=0;j<name.size();j++){
		if (i!=j){
			double xDiff = posX.get(j) - posX.get(i);
			double yDiff = posY.get(j) - posY.get(i);
			double xCenter = (posX.get(i) + posX.get(j)) / 2;
			double yCenter = (posY.get(i) + posY.get(j)) / 2;
			if ((xDiff * xDiff + yDiff * yDiff) < radius * radius){
				double difSize = Math.sqrt((xDiff * xDiff) + (yDiff * yDiff));
				double normalX = xDiff / difSize;
				double normalY = yDiff / difSize;
				posX.set(i, xCenter - ((normalX * radius) / 2.0));
				posY.set(i, yCenter - ((normalY * radius) / 2.0));
				posX.set(j, xCenter + ((normalX * radius) / 2.0));
				posY.set(j, yCenter + ((normalY * radius) / 2.0));
				double DiffSpeedX = accX.get(j) - accX.get(i);
				double DiffSpeedY = accY.get(j) - accY.get(i);
				double fScalar = (DiffSpeedX*normalX) + (DiffSpeedY*normalY);
				double NewSpeedX =  normalX * fScalar * speedLoss;
				double NewSpeedY =  normalY * fScalar * speedLoss;
				accX.set(i,accX.get(i) + (NewSpeedX));
				accY.set(i,accY.get(i) + (NewSpeedY));
				accX.set(j,accX.get(j) - (NewSpeedX));
				accY.set(j,accY.get(j) - (NewSpeedY));
			}
		}
	}
}
All that does is check for collisions between a list of identical circles, not even spheres. It keeps the circles from passing through each other, sets them so they look like they actually touched, and changes the speed appropriately (so that you could have a newton's cradle effect). It's completely unoptimized, and if you think that looks complex, it's not. That's actually as absolutely simple as it can possibly get.

In most cases, you have to balance out collision detection in some form, otherwise the computer's poor processor simply won't be able to handle it. This is part of why games just about never simulate completely realistic physics. Some take shortcuts and make it look realistic (e.g. Half Life 2, Crysis, etc), but if you pick at their engines enough, eventually, you find flaws where those shortcuts are.

Josh is going to have to take shortcuts somewhere. There won't be ridiculously accurate collisions system-wide, no matter what.
Last edited by Talvieno on Sun May 04, 2014 7:01 am, edited 2 times in total.
Have a question? Send me a PM! || I have a Patreon page up for REKT now! || People talking in IRC over the past two hours: Image
Image
Image
Post

Re: What is important to you? Many npc's or accurate collisi

#14
I'd prefer more NPCs. 'Accurate' collision is one of the reasons you see, for instance, buckets clipping through walls and getting stuck in your Elder Scrolls and Fallouts. Irregular shapes get messy, and we're not likely to see many 'regularly shaped' spaceships and asteroids.

I'm pretty confident Josh can craft something better than Bethesda, of course, but if something has to be sacrificed I think this is one of the better things to lose.
Post

Re: What is important to you? Many npc's or accurate collisi

#15
SyrusRayne wrote:I'd prefer more NPCs. 'Accurate' collision is one of the reasons you see, for instance, buckets clipping through walls and getting stuck in your Elder Scrolls and Fallouts.
That's a hazard with thin objects. There's not really that much of a way to get around it... at least not without slowing the game down. Fortunately for us, spaceships aren't paper-thin, and Josh's are made up of standard geometric shapes, which are really easy to get collisions with. Now, here's the fun part: there are tens of thousands of these geometric shapes. That'll kill your computer if you check them.

A fast way to do it might be to divide the star system into "sectors", and give each sector a list of the objects contained within, updated whenever a ship or object switches sectors. Distant sectors don't need to be checked - only the sectors directly around the player - and that cuts out a huge quantity of looping and distance checking. After that, only adjacent sectors need to be checked for collisions - but only for spheres around the objects (i.e., pretending all the ships are spheres, to see if they're close enough to collide). For any possible collisions that are detected, it runs an algorithm where it checks to see if the "collision meshes" are colliding - this would be faster than checking shape-by-shape - you simply create a "collision mesh" for each ship when it is created. Many games do this, as it's faster. If you want absolutely correct collisions, you can just check each geometric shape, and you could even write it in so there's a bit of realistic rebound physics (spinning, for instance) if you do it that way - but again, that'll slow it down. It's all a balancing act, and the more detailed you want your collisions, the more complex it's going to be. Convex shapes are pretty fast and easy, but it means no flying through gaps in a giant space station. Detail = complexity = slow.
Have a question? Send me a PM! || I have a Patreon page up for REKT now! || People talking in IRC over the past two hours: Image
Image
Image

Online Now

Users browsing this forum: No registered users and 6 guests

cron