How would I go about generating random platforms without intersection? I think garbage collection and maybe all that checking may be an issue. I've got the generating tiles part down, but not the intersection checking.
+1
A:
See a vaguely similar question I asked with regards to needing objects removed. The GC is the bane of my XNA existence. It's slow. It can create noticeable lag when it strikes. So my own personal advice is to not attempt good garbage collection but to try to avoid the need to garbage collect.
If your platforms are objects try to keep the references alive. If a platform goes off the screen don't delete it, just reuse it. Reposition it on the other side when a new platform is needed. At the beginning just create a number of platforms that you can use and reuse.
Bob
2010-03-18 16:32:50
+1
A:
How are your tiles (are these the things that can intersect?) described? There are many standard methods to check for intersecting objects, if they're axis-aligned boxes then it's dead simple.
boxes_intersect = ((a.min.x < b.max.x) && (a.max.x > b.min.x)) &&
((a.min.y < b.max.y) && (a.max.y > b.min.y)) &&
... for as many axes as you have
dash-tom-bang
2010-03-19 18:16:20
Yeah, it is simple, but I'm not sure how to keep it from slowing down since I have to perform this check on every object don't I?
DMan
2010-03-19 18:40:14
So yeah, this is a O(n^2) operation since you have to check every item against every other one. The right solution depends on the dataset, but "islands" might work ok. For that, keep track of groups of objects that are close together and might interact, then only do the expensive check against nearby things.In general, this is a tough problem to solve, and you're going to want to start solving it without dynamic memory. Reuse whatever you can, like Bob mentioned.One optimization you can make is to only check moving things. If everything's moving, well, you're screwed. :) Good luck!
dash-tom-bang
2010-03-20 00:41:16
A:
These easiest solution is to just place a tile randomly and then check to see if it collides with any other placed tiles. If it does, then just try placing it again. If the tile cannot be placed after N number of tries, then stop trying.
Obviously this is an O(n^2) solution, but you can reduce the complexity using a simple divide and conquer approach. When placing a tile, simply record the location in some sort of position relevant or gridded mapped data structure, tiles placed thereafter can then just check the data structure they are being placed into to see if there are any collisions, and potentially update it if the are added.
RodYan
2010-03-24 19:35:56