I took a break from working on Myriad last week, Tom was working on a breaking change to the UI system, and rather than work on something else I decided to take a break altogether. Why? I hear you asking, well I was thinking on a problem that I was eventually going to face with AI in Myriad, and decided to take a stab at solving it.

First some background on the problem, Myriad is going to have a lot of units, most of them are not under direct player control - rather they wander around and look for jobs to do. I need some way to manage all these AIs, and subsequently I need some way for these AIs to be in some way aware of each other in the world, a quick list of the top of my head:

• Formations (knowing the positions of squad mates)


• Taking cover (knowing the positions of enemies nearby)


• Attacking enemies (knowing the positions of enemies in range)

Basically, I need a way to efficiently make bounding sphere circles (get all things within this sphere). Sounds easy, except that if all units are simply stored in a big list I'm going to have to check every unit for every query, and of course many AIs will be making queries very frequently.

While I was thinking about this, I stumbled upon a paper about range search trees (unfortunately I can't find it again), a range search tree is basically a tree which maintains information about items in space, it's not quite how my system works but it was what inspired me.

So, how *does* my system work? Well I though, all I have to do is define a box, and add all items to that box, now if that box is subdivided to some depth, I add items only to the appropriate children and so on. To do a query is quite complex, but is very efficient (as many early out cases if possible)

Does the query area intersect this box?
-> Yes:
-> Does the query area totally contain this box?
-> -> Yes:
-> -> Add all items in this box to the answer
-> -> Return
-> -> No:
-> -> Does this box have children
-> -> -> Yes:
-> -> -> Query children
-> -> -> No:
-> -> -> Iterate through all members of this box, and check them individually against the query

As you can see, if the query area does not even intersect this box, nothing happens, if the query area completely contains this box all members are added without any checking, if the query merely intersects this box, then the query is passed onto children (which have a better chance of being totally contained), if there are no children then finally every member of the box is tested one by one against the query.

Simple! However, you know me, I like to keep things nice and complex. So I modified the system so that it works in N dimensions (for fun, because I have way to much time on my hands in the summer holidays). Then a added some more queries, rather than just querying if items are in a circle or a box I added a query for the intersection of the two (only return items in both the box and the circle).

I also support intersections of any given set of hypersphere and hyperrectangles, or even (the most complex and fun to implement), a query which returns only items in the intersection of a set of Hyper Spheres/Rectangles AND are not in any of another set of Hyper Spheres/Rectangles. Fun!

How can I use this for AI? Well so long as every AI is in the tree I can do queries like "Fetch every AI within range of sight of this unit, but not ones within this cloud of smoke" and other clever things ;)

Now for the pictures you've all been waiting for!


A circle query, successfully selecting all relevant items:



A box Query, successfully selecting all relevant items:



A combined intersection/exclusion query, selecting items in blue shapes but not in red shapes.