Castle Paradox Forum Index Castle Paradox

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 
 Gamelist   Review List   Song List   All Journals   Site Stats   Search Gamelist   IRC Chat Room

Collision detection

 
Post new topic   Reply to topic    Castle Paradox Forum Index -> HELP!
View previous topic :: View next topic  
Author Message
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA




Joined: 19 Feb 2003
Posts: 518
Location: Halifax

PostPosted: Mon Jun 07, 2010 6:22 am    Post subject: Collision detection Reply with quote

How is NPC collision detection handled in the OHR?

I ask because I'm trying to write up my own collision detection system.
Are there known collision detection systems that aren't super costly?

I'm working with slices you see, and I may be working with a lot of them ... say ... possibly ... 50+ per map.

I hope to have these slices freely moving at all times, and if two come within a certain radius of one another, there is a collision response.
Now what I *could* do is check the relative positioning of each slice to ALL the other slices every tick. So ... the cost goes up with the square of the number of slices. I don't think this is a very good thing.

I was also thinking of storing lists of slices that exist in a "neighborhood radius" of each maptile, and these lists would be updated each tick. That way, you only need to check the relative positioning of the slices within a list (for each given list).
This would be practically impossible without arrays and maptile extra data ... which don't exist.

Is there any other way?
_________________
Working on rain and cloud formation
Back to top
View user's profile Send private message
Rimudora
Psychopath yandere
Halloween 2006 Creativity Winner
Halloween 2006 Creativity Winner



Joined: 26 May 2005
Posts: 335

PostPosted: Mon Jun 07, 2010 6:51 am    Post subject: Reply with quote

If you're using slices, there's a script command that checks if any two slices are overlapped.

http://hamsterrepublic.com/ohrrpgce/index.php/Plot_Slice_collide.html

Depending on how you're using the slices, you might not have to check them *every* tick. Say.. if you have 50 slices, you can have something that checks collision for slices 1-25 the first tick, and then 26-50 on the next. It might be less accurate, but it'd cut the cost in half during any one tick.
Back to top
View user's profile Send private message Send e-mail
TMC
On the Verge of Insanity




Joined: 05 Apr 2003
Posts: 3240
Location: Matakana

PostPosted: Mon Jun 07, 2010 8:11 am    Post subject: Reply with quote

There's nothing special about the builtin NPC collision detection. Actually, it's pretty poor and allows NPCs to momentarily overlap as they move, especially when they have different walk speeds, which has always annoyed me.

----

Actually, for speed the command you want to use is find colliding slice. However, this command will still require time proportional to the square of the number of slices, and if you use getcount it does lots of redundant calculation. But 50^2 is absolutely nothing.

There are O(n log n) algorithms for finding all the collisions amongst objects in a set, so I plan to add an even faster collision detection function when arrays are implemented. But I don't think it will be needed until we start seeing hundreds to thousands of slices on a map.

Also, note that you can parent slices to different parents to help collision detection. Fo example in a scrolling shooter, if you give friendly units, friendly projectiles, enemy units, and enemy projectile different parents you will both dramatically speed up collision checking and probably greatly simplify you scripts too.
_________________
"It is so great it is insanely great."
Back to top
View user's profile Send private message Send e-mail
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA




Joined: 19 Feb 2003
Posts: 518
Location: Halifax

PostPosted: Mon Jun 07, 2010 9:28 am    Post subject: Reply with quote

Re. "find colliding slice":
What happens if I pass a value for argument "number" that is larger than the number of colliding slices? Does it return 0?

Hm ... it would be nice to categorize my slices into different parents, but I'm thinking I may be having most visible slices as children of a single slice. The reason for this is that I'm going to be using 3D coordinates for most of my slices, and so I need to have full control over the layering of the slices. I don't want to have it so that any one kind of slice is *always* in front of another.

However, with arrays, I should be able to keep lists of slices by category.

By the way, is there any way (other than globals) to store info on slices in a save file?
_________________
Working on rain and cloud formation
Back to top
View user's profile Send private message
TMC
On the Verge of Insanity




Joined: 05 Apr 2003
Posts: 3240
Location: Matakana

PostPosted: Mon Jun 07, 2010 9:04 pm    Post subject: Reply with quote

Bagne wrote:
Re. "find colliding slice":
What happens if I pass a value for argument "number" that is larger than the number of colliding slices? Does it return 0?


That's exactly what the documentation says.

Quote:
I don't want to have it so that any one kind of slice is *always* in front of another.


Ah, yeah. Arrays will be great for ending the tyranny of parent slices. I could add a command for searching for collisions with any of the slices in an array.

Quote:
By the way, is there any way (other than globals) to store info on slices in a save file?


James has just about finished the new save format, so you can expect to be able to save slices in the nearish future. (However I'm going to predict that there will probably will some small roadblocks to saving slices specifically.)
_________________
"It is so great it is insanely great."
Back to top
View user's profile Send private message Send e-mail
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA




Joined: 19 Feb 2003
Posts: 518
Location: Halifax

PostPosted: Tue Jun 08, 2010 4:03 am    Post subject: Reply with quote

Tubular.
_________________
Working on rain and cloud formation
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Castle Paradox Forum Index -> HELP! All times are GMT - 8 Hours
Page 1 of 1

 
Jump to:  
You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group