As a practical example, we’ve gone with having the world divided up in quadrants and sectors (each quadrant consists of quite a number of sectors), both on the server and client (although the client is only aware of the nearest sectors). With this setup we can register objects to sectors on the server and when a player requests information about their vicinity, they get info on the nearby sectors and thus also about the registered objects.
@normen said:
You will never want to know anything about "any object in my world at that location" at this scale, believe me.
Please, please, please, stop second-guessing what I want to do. My design choices are mine to make. They are no business of yours.
Let me make my own mistakes and find my own greatness.
Aping your mistakes and greatness would be pointless, that path is already being explored ;)
So:
Do you know of a way to do server-side location-based searching: yes or no?
If yes: what's the best way to do it?
I told you multiple times. You get a bunch of stations from your DB or entity system and then you have their world location in whatever format and you check which are in the range you need. That doesn’t have to happen at a “picking” level at all.
Then if you actually need a ray test there for your “trans-galaxy gun” or whatever :roll: you create the actual collision space for that part of the universe and check the collisions there for finer-grained information, that doesn’t have to happen at double precision as you know where you are already.
@toolforger said:
Do you know of a way to do server-side location-based searching: yes or no?
If yes: what's the best way to do it?
I estimated that there are approximately 1,123,964 different ways to do this. (roughly. ;))
Are you holding all of your objects in memory or are they in a database? (The first 563,126 approaches deal with in memory and the rest deal with in a database... with approximately 12-15 ways per database product)
How many total objects are there?
Are objects mostly 2D or all over the place in 3D? (ie: for space sims its still very common to have galaxies be sort of 2.5 D)
And even that is only scratching the surface of the assumptions we'd have to make to answer, I guess. So anything else you can think of to add will get you better answers.
Are objects sparsely located or clustered? How clustered/sparse?
What is the simulation space per servernode? a solarsystem or a galaxy or a planet + sourrounding space and moons?
Right now, I’m thinking of the whole game inside the RAM of a single server (not even with a database, just regular backups of the world state to an ordinary file).
The whole thing will span a vast order of magnitudes.
I want the design space unconstrained; lift a constraint, and the ideas will come. For example, I can think of interstellar objects - Kuiper belts, blackbodies, listening posts, picking up directional transmissions if you’re in the right spot even inside that vast emptiness; a chunked universe will make such things so much more work that game design will censor itself from even trying to do such stuff.
(And I don’t care in the least if the normens of this world think this is a ridiculous idea. I’ve been around for a few decades, and it did teach me the value of diversity.)
Enough philosopy 
Technically, I’m thinking along the following lines:
- Have an octree with double coordinates.
- Use an entity system. In-game position is just an entity component: a reference to an octree node. This allows replacing the location-based services with little (possibly even zero) impact on the rest of the system.
- An entity system is easier to split up across machines, too. The split could be done along location, or along component types, or whatever has least impact on throughput and latence.
- No database. Everything in RAM, a background process takes snapshots of the world state and saves them in standard flat files.
- Keep a snapshot per tick of the world, for the last 100 or 200 milliseconds. That's for lag compensation: interpret user commands in the world as it was when the user issued it.
- The last two point mean data structures that can be snapshotted without "stopping the world", so probably copy-on-write and/or immutable data structures.
Opinions welcome :)
The octree is probably not necessary and has several disadvantages.
Pick a grid size (or sizes) and then give coordinates a grid location. This is just math and is very fast. You don’t have to worry about having empty splits or any of that. A coordinate can easily go from cell to ID and back again.
As your ideas evolve, you might consider something like hyperSQL. It’s really fast and supports full memory cached tables.
http://hsqldb.org/
Writing my entity system component->sql layer only took a weekend and it automatically creates the tables from the component fields, etc… So far that was one of the best things I ever took the time to do.
:brainsout:
I am actually trying to help you. If you want to talk only about how you want to do it then the best way would be doing it first, then showing us and talking about it. (oh right, its not possible) Remember you came “to the normens of this world” for help and were asking for solutions, if it pisses you off that you don’t understand my answers I can understand that but bitch, please…
@normen: Oh, I’m not bitching. And believe me, I’m understanding well enough what you say.
You just don’t understand that I have no interest in adjusting my problem space to your solution space.
@pspeed: Yes, I’ve been considering H2 and hsqldb.
I’m not sure - what’s the benefit of a database over flat files?
I’ve been working with an Oracle database in the last three years, and mostly Mysql in the time before; I know where databases shine and where they suck.
I’m not sure that a game server is a use case where the shine applies, so I’m genuinely interested in your perspective there.
I didn’t mean to say I’m sold on an octree; other variants that I can think of are:
- A SortedMap (i.e. TreeMap or descendant) with Z-order on coordinates
- Either octree or TreeMap, with linear lists near the leaves
Anything with an O(log N) complexity for finding the next node given an arbitrary set of coordinates.
Plus routines for defining arbitrary shapes (regions), plus efficient collision detection code (i.e. given N objects, test whether any two overlap, and don't use more than O(N log N) time for that even if N approaches millions).
I could write that stuff myself, but I'd prefer to leverage existing code. jme's scene graph doesn't work because it's limited to float precision, and bullet seems to not scale to scenes with really many objects... so are there alternatives?
@toolforger said:
You just don't understand that I have no interest in adjusting my problem space to your solution space.
[...] ... so are there alternatives?
The thing you don't understand is that it's not my solution space. There is no computer system in this world that can solve the problems you forcibly create (just to please your brain to know its "really" the distance between two objects), you have to apply one of the many solutions we outlined. Just no way you can have a system computing millions of objects in realtime without partitioning, neither memory-wise nor processing-wise. If you could better describe what you actually want to achieve instead of demanding a solution for an unsolvable problem you might hear different answers.
hypersql is better than hand-rolled flat files only because you could easily swap it out for something bigger, you can have it all in RAM, and because it is already handling querying for you and might be doing it more efficiently. Keep in mind that this will be the fastest “database” you’ve ever used, especially as compared to Oracle. Not even in the same category.
The other nice thing is that I can pop open the hyperSQL GUI to look at my data without the game running.
The grid cell ID approach is nice because you can just throw the stuff into a hashmap based on the cell ID. You get constant-time lookup of things in a cell. From there you could partition further but that’s why I asked about sparseness. If you only ever have a couple hundred objects in a cell then linear searching is probably fine at that point. If not then you can always use a smaller grid size if your “space” allows that with your key precision.
@pspeed:
Hehe, yes, Oracle won’t fit, it’s not built for that kind of requirements anyway.
I have Hsqldb and H2 on my shortlist. (As I said, I’m not yet sold on any technology.) I see good points in favor of both, I don’t know which one would work better.
Neither has spatial queries, it seems - Hsqldb not at all, H2 just a Z-order index (that’s just the basis). I just stumbled over http://geoserver.org/display/GEOS/SpatialDBBox which says you can retrofit spatial to any database, which sounds good - I’ll have to take a closer look at that.
Whether I use hash maps, octrees or ArrayLists - I’ll keep that pluggable.
I.e. an entity system with a Location component that doesn’t leak any dependencies on the internal data structure. Just queries to find the next neighbour to a point, and to detect collision (spatial intersection) and stiction (spatial touching). And some API to convert coordinate values from and to internal string representation.
Just a heads-up: Hash maps aren’t as O(1) as many people think.
Insertion becomes O(log N) if you can’t predetermine size.
I’m not sure that the difference between O(1) and O(log N) is relevant enough to accept an architectural constraint like “know your hashmap sizes before you create them”. It’s usually constant factors that matter more - which means you have to benchmark and profile things.
Which, in turn, means to me that I’ll want to keep the data structure pluggable, so I can try out variations without having to rewrite everything.
The assumption was frequent look ups, relatively infrequent inserts. It’s hard to do better than a hash map when in ram.