Don

I take your point about copying a vector. It would be slightly less of a problem for a vector of pointers, perhaps, but it would be good to avoid altogether. But you give me a better idea. Given a unit U we would like to move: We (will) know the node N that contains the unit. Get the node P that is the parent of N. (Or the grandparent or higher, depends on the situation.) Traverse P. For each node under P, for each game object in that node, Call a function in the game object that calculates range to U. This eliminates the need to create a big vector of (pointers to) game objects and return them. And it permits us to keep the code for the tree and the game object in separate modules. But of course talk is cheap when I haven't delivered any code yet.

I'm reworking the tree along the lines you've described---though I will be hiding the details of the tree implementation from the game object. It should be possible to call a method on the game object that returns all the nearby game objects. And unless I (still) misunderstand, "nearby" is approximately "contained in my sibling nodes in the tree."

I understand how an adaptive tree would have fewer units per node. I don't think I get how that would save me work in detecting a collision. If I want to move a unit a step forward, surely I have to calculate whether it will collide with any nearby unit, yes? If there are many nearby units and they are scattered among several nodes, how is the calculation easier than if they are all in one node? If there are n units near me, it's O(n) either way, isn't it? To put the same confusion a different way: I thought the quad- or octree is supposed to act like a sparse array with one cell for each atomic point on the map. Maybe that's my mistaken assumption. At least I'm not suffering from the delusion that I get it.

For consistency, what would be the best source code directory for the octree code? I thought lib at first, but it seems special in some way.

Please elaborate on this. I understood the oct- or quadtree would be functioning as a sparse array, with a single cell at (x,y,z) corresponding to one leaf node in the tree and one "game object." But you make it sound as if you'd like to be able to subdivide the space further at runtime.

Warcraft 2, StarCraft, Warcraft 3, StarCraft 2 But I'm over Blizzard games because they insist on making them online-only.

Agree we can't infringe copyright, and agree there are probably some movie studios who wouldn't hesitate to sue their own customers for a quick buck. BUT, there are fair use exceptions to copyright. Something like fan fiction, for example, would be an example of fair use. Satirizing or commenting on LOTR is fair use. Non-commercial, transformative use of a character from LOTR in this game would be fair use. Of course if the studios decide to make fraudulent copyright claims, which happens often, we're just as screwed as if we were actual copyright infringers, and we don't have the means to defend ourselves. So for now I wouldn't take the risk of asserting our fair use rights, unless it was essential to the game.

I don't feel strongly either way about quad- versus octree. There's a strong efficiency argument for the quadtree, and there's a strong argument that an octree will allow us more realistic 3d modeling of the game world. I, for one, want to be able to fire arrows down from a highway overpass as my enemy marches underneath, but that probably won't happen any time soon. Perhaps I'll add a compile-time flag that turns the third dimension on and off, so my code is still useful after the argument is decided. Building an object pool sounds like a good idea, and a good enough reason for a custom implementation. Just so we're clear, you want an efficient sparse array, and all the culling, range finding, etc happens in other code, correct?

I see that there's not a consensus about whether an octree is The Way, but if the dev manager likes it I'm willing to go forward. I have some questions about what I'd be delivering. * I understand there are several different uses for an octree, including graphical rendering, route finding, and so on. That suggests the best interface is a pretty low-level one, e.g., I create an object of type Octree and then just treat it as a sparse array in three dimensions. Is that how you want to use it, or are there some operations (find a certain value? copy? prune off everything under a certain node?) that are going to be needed frequently enough to build it in? * What data types are likely to be stored in the nodes? * I've found an open source templated octree class. Maybe this project is already done, or maybe this implementation I've found is too slow. Can you suggest what operation(s) need to be especially quick for our purposes? Don

This was solved by uninstalling-reinstalling video drivers. Now I can play my games (woo) and build the 0ad code as well.

Ah. I think we're on the right track for two reasons. One, when I was trying to install the prerequisites, I remember thinking the build instructions were ambiguous about which OpenGL package I needed. Two, when I open the Nvidia X Server Settings application and hit OpenGL/GLX Information, the application crashes. What specific packages do I need to meet the OpenGL requirement?

After doing apt-get dist-upgrade I now have the cursor, menu text, music, and no graphics. If I start a game I get the minimap in the lower left, and a black main screen, with a greyscale conical shape at the center, FWIW. system_info.txt

That's just the changes from trying to build 0ad. The system_info.txt is attached.system_info.txt

As with http://trac.wildfiregames.com/ticket/1570 I get the black screen and the cursor in windowed mode. I don't get the same behavior if I start from the command line and use -vsync 1, in that test I get no 0ad cursor and no music, just full screen blackness. Fortunately synaptic keeps its history. Unfortunately the history is long. Installed the following packages: libwxbase2.8-dev (2.8.12.1-12) libwxgtk2.8-dev (2.8.12.1-12) wx-common (2.8.12.1-12) wx2.8-headers (2.8.12.1-12) Upgraded the following packages: libxcursor1 (1:1.1.13-1) to 1:1.1.13-1+deb7u1 libxfixes3 (1:5.0-4) to 1:5.0-4+deb7u1 libxrender1 (1:0.9.7-1) to 1:0.9.7-1+deb7u1 Installed the following packages: libxcursor-dev (1:1.1.13-1+deb7u1) libxfixes-dev (1:5.0-4+deb7u1) libxrender-dev (1:0.9.7-1+deb7u1) x11proto-fixes-dev (1:5.0-2) x11proto-render-dev (2:0.11.1-2) Installed the following packages: libogg-dev (1.3.0-4) libvorbis-dev (1.3.2-1.3) Upgraded the following packages: libcomerr2 (1.42.5-1) to 1.42.5-1.1 libcurl3-gnutls (7.26.0-1) to 7.26.0-1+wheezy2 libgcrypt11 (1.5.0-3) to 1.5.0-5 libgnutls26 (2.12.20-2) to 2.12.20-6 libgssapi-krb5-2 (1.10.1+dfsg-3) to 1.10.1+dfsg-5 libgssrpc4 (1.10.1+dfsg-3) to 1.10.1+dfsg-5 libk5crypto3 (1.10.1+dfsg-3) to 1.10.1+dfsg-5 libkrb5-3 (1.10.1+dfsg-3) to 1.10.1+dfsg-5 libkrb5support0 (1.10.1+dfsg-3) to 1.10.1+dfsg-5 libldap-2.4-2 (2.4.31-1) to 2.4.31-1+nmu2 Installed the following packages: comerr-dev (2.1-1.42.5-1.1) krb5-multidev (1.10.1+dfsg-5) libcurl4-gnutls-dev (7.26.0-1+wheezy2) libgcrypt11-dev (1.5.0-5) libgnutls-dev (2.12.20-6) libgnutls-openssl27 (2.12.20-6) libgnutlsxx27 (2.12.20-6) libgpg-error-dev (1.10-3.1) libidn11-dev (1.25-2) libkadm5clnt-mit8 (1.10.1+dfsg-5) libkadm5srv-mit8 (1.10.1+dfsg-5) libkdb5-6 (1.10.1+dfsg-5) libkrb5-dev (1.10.1+dfsg-5) libldap2-dev (2.4.31-1+nmu2) libp11-kit-dev (0.12-3) librtmp-dev (2.4+20111222.git4e06e21-1) libssh2-1-dev (1.4.2-1.1) libtasn1-3-dev (2.13-2) Upgraded the following packages: libavahi-client3 (0.6.31-1) to 0.6.31-2 libavahi-common3 (0.6.31-1) to 0.6.31-2 libfreetype6 (2.4.9-1) to 2.4.9-1.1 libgl1-mesa-glx (8.0.4-2) to 8.0.5-4+deb7u1 libglapi-mesa (8.0.4-2) to 8.0.5-4+deb7u1 libglib2.0-0 (2.33.12+really2.32.4-3) to 2.33.12+really2.32.4-5 libglib2.0-bin (2.33.12+really2.32.4-3) to 2.33.12+really2.32.4-5 libglu1-mesa (8.0.4-2) to 8.0.5-4+deb7u1 libjson0 (0.9-1.1) to 0.10-1.2 libpulse-mainloop-glib0 (2.0-6) to 2.0-6.1 libpulse0 (2.0-6) to 2.0-6.1 libxext6 (2:1.3.1-2) to 2:1.3.1-2+deb7u1 pulseaudio (2.0-6) to 2.0-6.1 pulseaudio-module-x11 (2.0-6) to 2.0-6.1 pulseaudio-utils (2.0-6) to 2.0-6.1 Installed the following packages: libasound2-dev (1.0.25-4) libavahi-client-dev (0.6.31-2) libavahi-common-dev (0.6.31-2) libcaca-dev (0.99.beta18-1) libdbus-1-dev (1.6.8-1) libdirectfb-dev (1.2.10.0-5) libdirectfb-extra (1.2.10.0-5) libfreetype6-dev (2.4.9-1.1) libgl1-mesa-dev (8.0.5-4+deb7u1) libglib2.0-dev (2.33.12+really2.32.4-5) libglu1-mesa-dev (8.0.5-4+deb7u1) libjpeg8-dev (8d-1) libpcre3-dev (1:8.30-5) libpcrecpp0 (1:8.30-5) libpng12-dev (1.2.49-1) libpulse-dev (2.0-6.1) libsdl1.2-dev (1.2.15-5) libslang2-dev (2.2.4-15) libts-dev (1.0-11) libxext-dev (2:1.3.1-2+deb7u1) x11proto-xext-dev (7.2.1-1) Installed the following packages: mesa-common-dev (8.0.5-4+deb7u1) Installed the following packages: libopenal-dev (1:1.14-4) Installed the following packages: cmake (2.8.9-1) cmake-data (2.8.9-1) emacsen-common (2.0.5) libcurl3 (7.26.0-1+wheezy2) libxmlrpc-core-c3 (1.16.33-3.2) Installed the following packages: zip (3.0-6) Upgraded the following packages: libxml2 (2.8.0+dfsg1-6) to 2.8.0+dfsg1-7+nmu1 Installed the following packages: libxml2-dev (2.8.0+dfsg1-7+nmu1) Upgraded the following packages: libboost-iostreams1.49.0 (1.49.0-3.1) to 1.49.0-3.2 libboost-program-options1.49.0 (1.49.0-3.1) to 1.49.0-3.2 libboost-thread1.49.0 (1.49.0-3.1) to 1.49.0-3.2 libicu48 (4.8.1.1-10) to 4.8.1.1-12 libpython2.7 (2.7.3~rc2-2.1) to 2.7.3-6 libssl1.0.0 (1.0.1c-4) to 1.0.1e-2 python (2.7.3~rc2-1) to 2.7.3-4 python-minimal (2.7.3~rc2-1) to 2.7.3-4 python2.7 (2.7.3~rc2-2.1) to 2.7.3-6 python2.7-minimal (2.7.3~rc2-2.1) to 2.7.3-6 Installed the following packages: gccxml (0.9.0+cvs20120420-4) libboost-all-dev (1.49.0.1) libboost-chrono-dev (1.49.0.1) libboost-chrono1.49-dev (1.49.0-3.2) libboost-chrono1.49.0 (1.49.0-3.2) libboost-date-time-dev (1.49.0.1) libboost-date-time1.49-dev (1.49.0-3.2) libboost-date-time1.49.0 (1.49.0-3.2) libboost-dev (1.49.0.1) libboost-filesystem-dev (1.49.0.1) libboost-filesystem1.49-dev (1.49.0-3.2) libboost-filesystem1.49.0 (1.49.0-3.2) libboost-graph-dev (1.49.0.1) libboost-graph-parallel-dev (1.49.0.1) libboost-graph-parallel1.49-dev (1.49.0-3.2) libboost-graph-parallel1.49.0 (1.49.0-3.2) libboost-graph1.49-dev (1.49.0-3.2) libboost-graph1.49.0 (1.49.0-3.2) libboost-iostreams-dev (1.49.0.1) libboost-iostreams1.49-dev (1.49.0-3.2) libboost-locale-dev (1.49.0.1) libboost-locale1.49-dev (1.49.0-3.2) libboost-locale1.49.0 (1.49.0-3.2) libboost-math-dev (1.49.0.1) libboost-math1.49-dev (1.49.0-3.2) libboost-math1.49.0 (1.49.0-3.2) libboost-mpi-dev (1.49.0.1) libboost-mpi-python-dev (1.49.0.1) libboost-mpi-python1.49-dev (1.49.0-3.2) libboost-mpi-python1.49.0 (1.49.0-3.2) libboost-mpi1.49-dev (1.49.0-3.2) libboost-mpi1.49.0 (1.49.0-3.2) libboost-program-options-dev (1.49.0.1) libboost-program-options1.49-dev (1.49.0-3.2) libboost-python-dev (1.49.0.1) libboost-python1.49-dev (1.49.0-3.2) libboost-python1.49.0 (1.49.0-3.2) libboost-random-dev (1.49.0.1) libboost-random1.49-dev (1.49.0-3.2) libboost-random1.49.0 (1.49.0-3.2) libboost-regex-dev (1.49.0.1) libboost-regex1.49-dev (1.49.0-3.2) libboost-serialization-dev (1.49.0.1) libboost-serialization1.49-dev (1.49.0-3.2) libboost-serialization1.49.0 (1.49.0-3.2) libboost-signals-dev (1.49.0.1) libboost-signals1.49-dev (1.49.0-3.2) libboost-system-dev (1.49.0.1) libboost-system1.49-dev (1.49.0-3.2) libboost-system1.49.0 (1.49.0-3.2) libboost-test-dev (1.49.0.1) libboost-test1.49-dev (1.49.0-3.2) libboost-test1.49.0 (1.49.0-3.2) libboost-thread-dev (1.49.0.1) libboost-thread1.49-dev (1.49.0-3.2) libboost-timer-dev (1.49.0.1) libboost-timer1.49-dev (1.49.0-3.2) libboost-timer1.49.0 (1.49.0-3.2) libboost-wave-dev (1.49.0.1) libboost-wave1.49-dev (1.49.0-3.2) libboost-wave1.49.0 (1.49.0-3.2) libboost1.49-dev (1.49.0-3.2) libexpat1-dev (2.1.0-1) libibverbs-dev (1.1.6-1) libibverbs1 (1.1.6-1) libicu-dev (4.8.1.1-12) libnuma1 (2.0.8~rc4-1) libopenmpi-dev (1.4.5-1) libopenmpi1.3 (1.4.5-1) libssl-dev (1.0.1e-2) libssl-doc (1.0.1e-2) libtorque2 (2.4.16+dfsg-1) mpi-default-dev (1.0.1) openmpi-common (1.4.5-1) python-dev (2.7.3-4) python2.7-dev (2.7.3-6) zlib1g-dev (1:1.2.7.dfsg-13) Other than that I didn't touch a thing!

I checked out the code from Subversion, installed several missing dependencies and successfully built 0ad. When I run the game I built, I get music, the 0ad cursor, and a black screen. I also have the game installed from a Debian package. It previously worked, but now gives the same black screen on startup. Is this a problem that others have seen before on Debian?

I'm a new 0ad player and I'm hooked pretty hard. Here's a suggestion that I don't see yet in the forum, at least not during the last 12 months. I'm in the middle of a game, I've got a couple different towns going, I'm sending some troops to hassle the enemy...and I hear a soldier's death groan. It's hard to localize the sound, because its loudness is the same no matter what part of the map is in view. It would be nice if a sound that was "distant" (relative to the current view) was fainter than a sound that was "close." There might be an easier way to find out where a noise came from, perhaps a visual cue on the minimap.

Has someone taken up the octree project? This seems like a nice, self-contained project for a new volunteer, and I'd like to pick it up. I've been working full time as a software developer for about 17 years now, mostly in C, C++, and the last year in Objective-C. I've done quite a bit of shell programming and Python, which I imagine won't be useful with 0ad. Still feel like a JavaScript newb but I do see it on the job. Very comfortable with Subversion. I haven't done any game development, which is actually one of the reasons I'd like to work on a more abstract module like this one. I get that it can be used to represent a 3d space, but I'm ignorant of how we would go from the data structure to, say, a rendered scene. I'll go ahead and get the source checked out and building. In the meantime, I'd appreciate it if someone from the team could give me a more detailed idea of the interface you need. I'm also curious to know why the existing FOSS implementations aren't what we need. (Licensing?) Don