Quadtrees… You’re doing it wrong!
In the previous post a member made a great comment suggesting the use of an existing structure for subdivision of space (also covered slightly in the previous post). The suggestion was the use of either a quadtree or an octree which are both very similar. I am the first to admit my knowledge of both is actually quite limited (or rather it was) which is why I went ahead and started reading up before I got too far into my own methods of subdividing the space. Upon further review I think a quadtree will truly work best for what I am trying to do.
Most of the following information is from GameDev.net which has tons of amazing articles / how-to’s / etc… on everything gaming related. Here’s the quick and dirty on what a quadtree is an how it’s going to help speed things up. First let’s look at my laughable 1 minute drawing of RedRidge in Photoshop:
What’s that I’m eating? Looks like a foot!
Well it looks like I may have put my foot in my mouth a bit, seems like I keep posting to revise my previous statements. In working through the code to make the changes mentioned in the other post I have found quite a few issues that need to be worked through. The truth is that the code is quickly approaching spaghetti factory again which is something I seriously want to avoid. As such I am busy refactoring and updating the code to have a much cleaner and more portable setup.
Read the rest of this entry »
The SVN is up!
The SVN is up at http://www.mpqnav.com/svn with public read access (no username or password required). It will be used to keep the latest version of working source from now on. Never used SVN before? That’s OK, it’s pretty easy.
- Download TortoiseSVN
- Install TortoiseSVN
- Create a new folder where you wish to keep the SVN files.
- Enter that folder, and then Right-Click somewhere in it. You should have a TortiseSVN flyout in your new right click window.
- Right above that is (or should be) an option to check, select that.
- Enter the SVN location from above.
- Watch it go!
- Now to update at any time, right click the folder and select the update option.
Enjoy!
I lied..
Well only a little bit. In my mindless ramblings on this blog I realized that I have strayed a bit from the original plan and after much meditation in a garden hidden in the depths of Japan I have concluded that the original idea was for the best and it should be kept that way. Which idea am I speaking of? That would be the distance between the points in our mesh.
In my hurry to get things done I had let this concept slip my mind a bit. Currently in our method to find walkable points we simply use the vertices of the triangles that build our ADT. This is all good and well if we wanted a resolution of 4.166~ units for our mesh, but that’s a pretty big amount. As I spoke about previously I am aiming for an initial resolution of .6 units (roughly 1/7th of the 4.166).
The forums work! Oh yeah, progress update as well!
Well first things first, a bit of a progress update. I am busy coding at the moment but thought I’d pop in and say hello to the readers that I have and let you know I am planning on a fun update this weekend. I would love to have my OBB - Triangle collision complete but it needs more testing so I’m not 100% sure I can get that out this weekend, what I can get out for sure (pending a natural disaster or the girlfriend surprising me with “here’s $10,000 go have fun”) is getting walkable connections between the standable points we found earlier.
Now before you get too excited keep in mind that because I’m not using OBB - Triangle collision these will be done via OBB - OBB collision. They will be 100% accurate, but not as detailed as they could be. What’s that mean? It means any walkable path that we find we can indeed walk on, but we won’t be finding all the walkable paths just yet. The reason for this is really just CPU based. We only have so much processing power in a machine, and unless we’re all sitting on super computers (which we’re getting close to these days) we want to use it as best we can. As such we want to start with simple tests (OBB OBB for example) and then move onto more involved tests (say OBB - Triangle or Triangle - Triangle) tests.
Forums up for real this time & Minor Update!
Well I wanted to put something up to let people know this project certainly hasn’t gone dark, just hitting that point where things are beginning to be a bit more difficult and as such updates are fewer and farther between. Work continues as always with a bit of a slowed pace to keep up with my day job (otherwise it’s back to my parent’s basement) but it is moving along.
Currently I am still tweaking and trying out an algorithm that I ported from C++ to C# for OBB - Triangle intersection. The fun part is it uses a seperating axis theorem to do the test (much like our OBB OBB intersection) but it requires variables in a bit of a different format then what we use. As such I have to convert the variables over each time which is really a waste of computing power. I have been looking over it to try and write it myself after some research into how the separating axis theorem actually works but no promises on that.
The forums are now up and skinned in with the rest of the site for the most part. Still needs some touches here and there but they should be fine for now. Currently there’s no login sharing between the forums and the blog (sorry) but it’s on my to-do list at a later point. I invite you to stop by the forums if you have any questions as they’re a great tool for community discussion. I will also probably be moving the downloads over to the forum in an evil attempt to force you to register. I’m a jerk and a forum addict, what can I say?
I have been debating putting up a SVN which I most likely will do to allow people to grab the latest source quick and easy and allow me to post bleeding edge updates for those that want to play without an explanation. Drop a comment/e-mail and let me know if you think it’d be something useful to you or not.
Well I shall end with a small trivia question. If you don’t get the question after reading it, fear not, you’re just not cool enough I guess.
Welcome MMOwned.com readers!
I was asked to provide proof that I am actually dejavu11 over at the MMOwned.com Forums and as such here’s my nifty this is dejavu11 post to prove it! An empty post wouldn’t be much fun so here’s another great picture:
When OBB’s Collide!
Quick, somebody cover When Worlds Collide for me (by Powerman 5000 for those that just plain aren’t cool). As mentioned in the previous post today we’re going to be discussing OBB’s (Orientated Bounding Boxes) and how to tell if two of them collide or not. Luckily for us I was able to come across a great OBB class for XNA/C# on the Internet from ZiggyWare located here. All props on saving me so much time and loss of sleep go to them on this one.
In addition I’ve done a lot of code cleanup and started commenting everything (commenting more as I speak) so it should help now that our code base is getting larger.
Code Cleanup Baby!
I’ve had a lot of “what’s next” questions in IRC lately so here’s the current breakdown:
- Major code cleanup before I post any more source (it’s starting to get ugly again which I don’t want).
- Proper commenting throughout for any late comers to the project.
- New post on finding points you can stand on without falling or hitting anything’s bounding boxes.
- Further investigation into actual movement collision checking (possible change of plans in how I am going to try it).
Of course there’s lots more that has to be done after that, but that’ll give a pretty good overview.
As far as timeline goes I’d like to have all four taken care of some time this weekend.
In the meantime, here’s a freaking awesome picture:
Bit of an Intermission and some General Discussion
Well real life has been calling here lately which has slowed things down a bit, in addition I am now entering new territory in the coding (meaning collision detection) that I haven’t done before starting this blog. As such it takes a while longer for me to get to the next place in the code and then post how it is done and why I did it the way I did. Thus the time between posts will most likely increase. I do still employ you to contact me with any questions or pop in on IRC at #mpanav irc.lavishsoft.com:6667!
This post will have little if any code and will be about the general theories behind collision detection as well as the current problems that I face.