More quadtree poking. Currently items can be dragged and dropped around the quadtree area. Actually the only items a small rectangle drawn in using GDI, it lights up yellow when the mouse moves over it.
The codes become quite unclean. Here's the most horrible thing in it at the moment:

        void OnNodeWantsToChangePosition(INode n, float x, float y)
        {
            this.RemoveNode((T)n);
            n.UnsafeSetPosition(x, y);
            this.AddNode((T)n);
        }

Not very elegant casts that really shouldn't be required. Moving through a quadtree isn't very efficent, which is cool because they're generally for static stuff (my items). So when to move something in a quad I take it out of the tree, changes it position then replace it in the tree.




Still quite busy - I'll be going to Tokyo on the 31st for five days before returning to Old Bilayati. Upon arriving I guess I'll be quite busy again for a while. And soon I'll start University doing a masters in game programming - I'm considering doing a write up of all lectures here, so that's something to look forward to.

A vibrating blue squirrel

Still quite busy - I'll be going to Tokyo on the 31st for five days before returning to Old Bilayati. Upon arriving I guess I'll be quite busy again for a while. And soon I'll start University doing a masters in game programming - I'm considering doing a write up of all lectures here, so that's something to look forward to.

Today I've done a little hacking with the quad tree - well not really, I've created a windows application that makes use of the quad tree library just to make sure it's working as expected - seems ok.

I'm still adding a few notes over here, it's all quite jumbled but could make interesting reading if you have some time.

My goal at the moment is to have the quad tree stuff working solidly. This allows me to get a decent inventory system up and running. It's hard to concentrate as I'm making lots of goodbyes, trashing large amounts of stuff and all that.

'You ever put a full-length mirror on the floor, and then have a dog stand on it?'

Things may become slow here as I'm leaving my job and returning to England. So I have to do lots of "stuff".

A redness sensation

Currently playing with some Quadtree code, I want to add items to the render demo but I also want them to be able to select them with the mouse. The quadtree is also one of the large untackled chunks of Einfall stage 3. It's early stages and I'm working on a basic library version first.

Anyway here's my small description of what and why of the Quadtree.

Let's say you have a map with a few hundred items, candle sticks, dogs, rooms, people.

Let's call in 500.

The naive collision detection goes like so: foreach(item in items) DoWeCollide?

That's 500 comparisons to see if a single object collides, or if your mouse intersects an item. That's a lot. Imagine 50 NPCs are moving thats 50*500 comparisons every frame. A big number.

Oh no, what can we do this is the end of games as we know it!
Yes, it does seem that way ... but wait there's our hero QuadTree!

In a quad tree you split the map up into regions. Cut the map in half vertically and horizontally and you get four equal size regions. Now cut those regions into four, and perhaps once more. So we now have nest regions.

First Cuts
Region1
SubRegion1
SubRegion2
SubRegion3
Subregion4
Region2
...
Region3
...
Region4
...

So we have the above type of regions, notice the hierarchy we've got going on, admire that hierarchy.

Right, now our collision detection is more a conversion like so:

NPC> Hey, First Cuts, do I collide with any of your regions.
First Cuts> Why yes, yes you do, you collide with two of them I'm afraid. Region1 and Region2.
*NPC goes to talk to Region1 and 2
NPC> Hey, Region1 and Region 2 so I collide with any of your subregions.
Region1> You collide with two of mine.
Region2> And two of mine two!
NPC> Okay, time to check if I collide with any objects in those four regions!

"Wait, wait, wait," you might sputter "stop the science train Doctor Scientopolis, what about items bigger than one subregion. What if I have castle that took up half the map?"

Well, Jimmy, the castle would exist at the very bottom of the quadtree - but crucially it would exist in more than one subsubregion. You could write special code, not to attempt an intersect with an object more than once, if efficency is worrying you.

Region1
SubRegion1
-Castle
SubRegion2
-Castle
SubRegion3
-Castle
SubRegion4
-Castle
etc.

So what we saved, let's say you have your quadtree four layers deep (how deep depends on the dimensions of your map and number of your items), then in the minimum case you'll compare each moving object 4, times once per each region. That's a lot better than the 500 we had at the start.

-What about items that span many regions - well they're still added at the lowest subregion - they may be in more than one subregion pool.

In my game I think I want circles, rectangles, points and polygons. It's a nice finite list. I will have an object called intersectCheck which will handle intersect checks between these objects.

Celestial ninja syndrome

Movement's in! Yay. I didn't think I was going to get it finished by this weekend as I spent all of today cleaning my flat (as I'm leaving soon). Anyway all done. Mysteriously it seems to cut into the framerate more than expected so I'll have a look into that.

Here's an NPC brain (which could easily be swapped out for a brain that took input from the keyboard or something). It moves one tile down then stops.

public class WanderBrain : IBrain
{
    bool tempHaveMoved = false;
    #region IBrain Members

    public void Process(double elapsedTime, Entity entity, IEntityMap eMap)
    {
        if (!entity.Mover.Moving && !tempHaveMoved)
        {
            entity.Mover.Move(Direction.down, eMap);
            tempHaveMoved = true;
        }
    }

    #endregion
}

(I'm trying out the component model for my entities, current components that are required are a brain, I already use pretty much the same setup in einfall, and a mover that handles how the entity moves over the tilemap. I haven't put general components in yet.)

So suddenly I'm doing tile based movement where as before I had free wandering :D Still I can have freewandering for the player character and eveyone else locked into the tyranny of tile movement.

Anyway overall much much faster than einfall. Not done quite yet though ... I want to add items that will sit on the tiles. I'll probably also add some simple loading and saving stuff. Oh and I'll make the bottom set of tiles a static vertex buffer with a dirty flag - this should keep things faster!