Okay, roads and water optimized! It turns out, building the equivalent of Google Maps is hard.
But now, everything is rendering, and I can continue preparing the game for beta and working on gameplay/appearance.
Look at that shit. Look at those roads. Oh yeah.
I realized - it was perhaps a little early to celebrate - hence why no video yet. The ported polygon offset algorithm did have some bugs (or at least I thought, but nope - keep reading), it seems as shown:
Maybe better illustrated if the road itself is a random color:
So how do we debug this, and find the data set that represents the segment rendered wrong? Well, we can somehow render ids along the paths which might be a lot of work - OR - we can just use the random colors. Log a map of color -> line JSON to console and then pick the corresponding color from the screen.
Sadly I could not get this to work. I set the ambient lighting to “full white”:
environment.set(new ColorAttribute(ColorAttribute.AmbientLight, 1, 1, 1, 1f));
And got the hex value for a clicked pixel:
int pixel = ScreenUtils.getFrameBufferPixmap(0,0, Gdx.graphics.getBackBufferWidth(), Gdx.graphics.getBackBufferHeight()).getPixel(screenX, screenY);
Color color = new Color(pixel);
System.out.println(String.format("Clicked pixels %s", color.toString()));
But no luck.
So I wrote some code to generate textures as PNG files that I could then apply to the roads. The images had identifiers on them. However, they just render as black, for some reason.
So I resorted to the tried and true mechanism of rendering just one random segment and restarting the game until I got something funky. Finally I did, and it dawned to me what the actual problem is. See here:
This looks like one crazy road right? Wrong. It’s two roads, in the same feature in the same segment. I’m not sure why the data is provided to me this way, but if you look closely at the top and bottom you’ll see the center of the actual roads. The library I ported is happily joining the ends, but that’s not what we want. So we just have to pass the correct data. Here’s that more of that tile with everything broken, except this time I render lines between the end points the library sees to confirm the theory:
Then, let’s fix the data transformation. Much better!
Here’s the original area shown above:
…and finally some cities…
EDIT1: I took these screenshots with the debug lighting enabled and directional lighting disabled - so buildings may look a little funny.
Roads have never been this cool
Thanks Gjallar 
Video oopdate:
Fantastic progress!
About the two views that you plan on doing: a new zoomed in view and the current zoomed out view, have you considered just continuing with the zoomed out one which plays to your programming skills and doesn’t require lots of art assets?
Talk to @princec and others about feature creep and the extreme difficulty of making 3d art look consistent without an expensive and time consuming art department.
Apologies for the unsolicited advice.
Yes I’ve definitely considered that, and that’s what I’ll do for the first beta. Likely the “zoomed in” view will just have different sized models (creeps). In reality the priorities are:
Periodic NPC seeding is done. Just had to change some provider classes to use atomic updates to avoid race conditions.
Anybody ever run multiple instances of a libgdx app in Intellij with Gradle? Even with “Allow Parallel Run” it doesn’t work for me - it waits until I close the first one to open the second…
I’ve ran several instances with a fresh setup of libgdx, sometimes it will run both right away, other times it will wait on the other one to close before opening. Have you tried opening up multiple at once or one after the other? I’ve found more success opening them up in quick succession, then opening up one and waiting a bit before opening the other.
I actually think this is Gradle’s or Intellij’s fault, not libgdx…
I have to run two separate run configs at once. Even compound run configurations don’t work! Pretty sure it’s Gradle’s fault - I can see Intellij has fired off both builds, but the second waits.
Was able to make it work with https://plugins.jetbrains.com/plugin/7248-multirun
Intellij’s built in “Compound” run configurations don’t work with our Gradle setup. I am not sure what about the build configuration makes it not work…
As an update, I’ve been working on synchronizing attacks with the client and the server, and have made great progress. However, I’m working a lot on fastcomments.com a quite bit - I think I’ll be back on TDWorld next week.
Productive Sunday - getting attacks more accurate between server/client.
I’m now working on converting from the reactive version of the RTree library I’m using to the synchronous one, because I’m trying to debug the reactive one and it is not easy. The synchronous one also seems more up to date.
I have found the RTree library can be about 9 meters off (about 0.000081 nautical degrees) when searching, which is not good. I’m using doubles too, just to be sure.
On debugging the library, I found that:
EDIT - Moved to newer version of library, did not solve issue, but at least easier to debug now.
In light of difficulties with this library, and the fact that the other libraries I’m finding for doing geo-spacial queries are either very heavy (whole in memory databases) or very generic with lots of overhead per query, I’m rolling my own. What I need is very simple, and I can optimize for my use case very well.
I need to do potentially millions of queries a second on commodity hardware. I could do that today, with my shard mechanism splitting work across CPU cores, and I will keep that, however we can do a lot better.
I’ve been building out the backend for a year so I know what I need. Using a library was a good idea in the beginning as it helped me get started faster, but now it’s holding the idea back.
So, that’s my weekend project.
First pass of geospatial query engine works! I’ve verified its accuracy down to a few feet.
Here is an example of the “optimized” search API where when you store an object with a range, it pre-calculates the nodes in the grid that that node can reach by calculating its bounding box, rather than doing the search every time. Also, it is not immutable like the RTree library. One downside of the RTree I was using was that every add or delete created a new tree, which meant constructing a new tree every time a creep moved, spawned, or reached its destination. This was still fairly fast, but a mutable data structure has the opportunity to be much faster (with the downside of having to deal with concurrency, but the engine handles that).
We also have the advantage of having to move creeps between “nodes” in this structure much less often, so less moving memory around and potential cache misses.
GridIndex<PositionDouble> positionGridDB = new GridIndex<>(15); // 15 = slippy tile zoom level
Tower tower = new Tower();
tower.range = 30;
tower.position = new Position(10, 10);
PositionDouble positionA = new PositionDouble(10, 10);
PositionDouble positionB = new PositionDouble(10.0 + PositionUtil.metersToWorldDegrees(29), (10.0 + PositionUtil.metersToWorldDegrees(29)));
PositionDouble positionC = new PositionDouble(10.0 + PositionUtil.metersToWorldDegrees(35), (10.0 + PositionUtil.metersToWorldDegrees(35)));
CellItem<PositionDouble> resultA = positionGridDB.addRanged(positionA, positionA, tower.range);
positionGridDB.addRanged(positionB, positionB, tower.range);
positionGridDB.addRanged(positionC, positionC, tower.range);
List<PositionDouble> positions = positionGridDB.searchRangedMetersInCells(positionA, tower.range, resultA.cellIdsIntersecting);
assertEquals(2, positions.size());
assertTrue(positions.contains(positionA));
assertTrue(positions.contains(positionB));
Here I’m doing a weird thing and storing the Position objects themselves in the structure. How it will work in the real world is a bit different - you have separate grids for Towers and Creeps, but they are joined. When you add a ranged item to the Tower grid, you get back the cells that the tower can reach. When you query the Creep grid, you pass in those cell ids to optimize the query, at the expense of memory.
Remaining work:
Sounds cool. Will be great to see what the performance improvement is. I’ve always found that the graphics side is always the performance bottle neck and I work hardest on improving that. Sounds like you’re an expert with that already though and have squeezed a lot of performance out already.
Interesting that the old method based on the business geospatial code was so inefficient, throwing away the whole structure and re-building every time something changed.
One problem I stuffed up when trying to squeeze out performance from similar spatial code was to over-write each moving unit’s world coordinates every update frame.
The better way to do it is to update a transformation (translation and rotation) matrix every frame, and after subtracting the unit’s original world coordinates from the camera’s world coords, then apply the unit’s transform matrix to draw it.
That way you don’t get cumulating floating point errors which can be quite severe when the unit’s world (x,y) coordinates are say (10234123234.213, 32143221314.234) and the translation every frame is say 0.0000000001 which results in rounding problems when using floats or doubles, showing up as units that just don’t move because the least significant digits (the translation) are being ignored.
Cheers,
Keith
Hey Keith,
The old structure was fundamentally wrong for what I’m doing, and didn’t work. I could have forked it and fixed it, but I’ve been fighting it for a long time and the complexity in the library makes it hard to understand why simple bounding box queries return weird results.
The new structure is done, performs better from the extreme workloads I’ve tested (30k + creeps and thousands of towers in one square KM), and is actually accurate. I’m working on some charts that I’ll put up after work.
The graphics side has some bottlenecks too once the number of creeps goes above about 20k, but that is a separate issue. I already do the movement calculations on a separate thread, so for some reason rendering is slow.
Here’s the benchmark of tick times between the R-Tree and my custom Geohash index.
As you can see, creep traveling is faster but searching for creeps from a position is a little slower in some cases, with an overall improvement. This makes sense, since with the RTree library there is more overhead in creating a new tree with moving a creep vs with just updating some data in the Creep object in my library, until the creep moves out of its current “hash”.
I’m also using a ConcurrentHashMap and a CopyOnWriteArrayList to be extra safe, but I may do some testing and see where I am accessing the shard across threads - those cases are the minority and probably I can just add some locks in the “cold” paths and get rid of the CopyOnWriteArrayList.
Below 10k creeps in a tile, my implementation is faster. Beyond that right now, the performance falls off. That’s not really a problem as that’s an extreme case. I still have some optimization I can do, but I think I’m ready to move on to getting the beta out.
Remember that our original goal was accuracy, and performance was a stretch goal. So I’m glad we have almost equal performance, with the opportunity to go further.
