TDWorld Development Thread

[HappyHydra]

This thread will be a continuation of my posts from here.

What is TDWorld?
TDWorld stands for “Tower Defense World” It is aiming to be a location based tower defense game where you take over real-world buildings to create towers and use real-world roads as connections between the towers. When you take over buildings, and link them, it increases your economy in the game (you get credits for each economy creep that reaches its destination).

Story and Factions
The game is based on an upcoming book I have been writing, Doubleshear.

There are two factions - play as either The Dwell - an organization bent on taking over the world - or the Uprising. Each faction has its own strengths and weaknesses (like tower strength, build time, tech tree, creeps, etc).

Conflict
Towers shoot nearby creeps, and eventually you’ll be able to build attack creeps as well. Eventually there will be incentives for taking over a geographic region.

Technology
The backend and client are written entirely in Java. The backend is part application layer, part pub-sub system, part game-engine, and part database. These things have to be tightly coupled for optimization reasons as we are essentially doing a global traffic simulation with towers shooting the “traffic” (creeps). There are also lots of little utilities and services, mostly in JS. The simulation is broken into shards which for the most part, depending on how I design the gameplay, you won’t notice while playing the game. These shards can be orchestrated across servers to help the game scale to many concurrent connections. Think of a sharded database, except the shards can dynamically move around while you’re using it.

The rendering side of things utilizes libgdx. It features a custom render object pipeline / queuing system to quickly inject hundreds of towers/roads/etc into the scene.

In order to render the world, a custom map rendering engine was developed on top of libgdx. We get building data and road as meta data from various services, put it together, and at run-time construct polygons out of it.

Update Schedule
I have no guarantees other than I’ll have a beta out this year, and I want the game to be ready for when the whole corona-virus situation clears up as people will be itching to get outside.

While already out of date, a quick background on the game is here:

TDWorld Update #4 8/3/2020 Update - Capturing and Linking Buildings

[HappyHydra]

Update - I had to mostly work on FastComments.com this week, but I’m back on TDWorld now.

[HappyHydra]

Water rendering update…
Finally getting all pieces of water I need in the world, except for oceans.

Here’s Pittsburgh PA:

And here’s the San Francisco Airport:

I had to update the service between my backend and one of the services that serves me map data to split multipolygons into sets of three-dimensional matrixes - otherwise they would get ignored.

Also, I had a bug where I was passing the result of dividing two integers to Math.max without casting to doubles. Doh!

After that all the features I need are finally rendered. Still lots of TODOs with water:

• Split polygons between intersecting vertices (you’ll see the water is overlapping the divide of the river in the first pic - that’s why)
• Derive oceans from blank tile + surrounded by water, since the tile service won’t send me ocean tiles at the slippy zoom level I want to use.
• Render water ways - similar problem I have with roads - will probably do something like this.

[HappyHydra]

Was looking at the data I get for Aeroways (airport run ways/roads).

Sometimes I get the data as polygons, sometimes as lines…

Rainbow colors for debugging…

[HappyHydra]

Update - been working on polygon joining. Basically, for larger buildings I get the data in chunks. A wall here, a room here, and for the most part no identifier in the data to join them since it’s just geospacial outlines… When you select the building to build a tower, you should just select the whole thing.

For example, for the SF airport, a terminal should not able to be its own tower:

So now, for example for the SF airport - the whole thing would become one big tower (thus a very rewarding thing to capture, since it will be very hard).

Obviously there are still a couple things wrong with this polygon, but ignoring that for a bit while I get the “joining working”. It’s a bit of a tough problem, because you have to handle transient intersections too! Basically, where “<>” means “intersects”:

  For: A <> B <> C
  We get: A -> [B, C]

Anyway, that’s done, next is to handle intersections across tiles which are the “big chunks” that I get the sets of features from.

So for example, in this picture is only one part of the SF airport. If I load the whole thing up it breaks since the polygons are across tiles:

Hopefully I can figure that out tomorrow. Shouldn’t be too bad. It’s only a little challenging because I don’t have all of the data all of the time - I have to fetch them (which I then cache).

Oh also, water/oceans are starting to come together. Some bugs in interpreting the data still though.

I’ve also bought a book on OpenGL 4 Shaders which I’m hoping will be useful when I decide to try to make the game look good.

[HappyHydra]

Building polygons are now joined across tiles! This is all done in the backend. There are still a couple of synchronization bugs I’m working out, so a little early to celebrate, but a huge milestone.

Observe - you take take the SF airport as one whole building!

[HappyHydra]

Render quality update! No, I didn’t get side tracked from joining building polygons across tiles. That I actually worked out, I’m just working on optimizing it.

I fixed the render quality by accident while trying to figure out where some “extra” building body parts were coming from during debugging the “building polygon joining across chunks”. I really should pick a cooler name for that!

The water ways in Pittsburgh PA render nicely:

Same with the water around the SFO airport (mostly) - and the airport itself.

No video update yet. I’ll have a video once I get the building-polygon-joining-across-chunks optimized.

[HappyHydra]

Still working on joining buildings across chunks. Works reliably now, but not smooth enough yet for a video demo.

Added a directional light for the sun (I never new directional lights had no position, go figure).

Here’s a certain famous theme park in LA with a ride selected - showing off polygon joining.

[HappyHydra]

Deterministic joining is now a success. Just some edge cases to handle on the client now, like if the client gets a tile before tiles next to it have finished “collapsing” into nearby tiles.

Some fun pictures from debugging during development. Used random colors to identify polygons and adjusted Y value if a polygon got rerendered, identified by its vectors.

[HappyHydra]

Building joining is working, but want to have roads looking nice before the next video update so working on that.

To create polygons from the geospatial data I have to implement a line offset algorithm. This is a bit tough, so I’m porting a popular library from JS to Java. This library depends heavily on a certain impl. of a red black tree too however, so I’m porting that too. Should have roads looking nice and be filled in polygons very soon!

Road line vectors (sequence of points) -> offset to create vectors for polygon -> Delaunay triangulation.

[CommanderKeith]

Hi,
Cool project.
For line offsetting, which is also commonly called buffering for polygons, look up JTS Java topology suite:
https://locationtech.github.io/jts/javadoc/org/locationtech/jts/operation/buffer/OffsetCurveBuilder.html

They have robust algorithms already in Java.
Cheers,
Keith

[HappyHydra]

Thanks, awesome! I searched for a while but couldn’t find a good algorithm in Java. I’ll give theirs a try.

[HappyHydra]

Thanks, Commander I have filled roads now, albeit with some new issues…

Sometimes, the roads are not rendered very well… I’m guessing for some reason the set of coordinates I’m passing to the triangulator are invalid.

When we debug, with each road a different color, we see:

I’m using Libgdx’s EarClippingTriangulator, the DelaunayTriangulator doesn’t give me anything, which should be a clue the coordinates are invalid / not closed. I’ll look more this afternoon.

[HappyHydra]

So, it seems like JTS is pretty primitive in how it handles some shapes. It does not seem robust at all, unless I am missing some configuration or some other part of the library that can handle cases like this:

The library I was porting handles cases like this:

w8r/polygon-offset

I’m almost done with the port, so I guess I’ll finish it and compare the results.

[HappyHydra]

It seems like if I want to go the JTS route - I should be looking at this: https://locationtech.github.io/jts/javadoc/org/locationtech/jts/operation/polygonize/Polygonizer.html#Polygonizer--

Just trying to figure out the api…

EDIT1: Using the Poygonizer I just end up with areas like shown above completely stripped away Still exploring.

[CommanderKeith]

I’m sorry it’s not fitting your needs.

I’d guess that perhaps with your very detailed data and the small changes in coordinates between points, some ‘flattening’ is probably going on that combines close points together.

Looking at the source, I’d say line 220 is responsible but I may be wrong:

locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/operation/buffer/OffsetCurveBuilder.java

The PrecisionModel and BufferParamaters could be worth double checking or playing with too, particularly the cap joins (or mitres or bevels? not sure what they’re called). From your screenshot, it looks like small angles are being flattened:

https://locationtech.github.io/jts/javadoc/org/locationtech/jts/operation/buffer/BufferParameters.html
https://locationtech.github.io/jts/javadoc/org/locationtech/jts/geom/PrecisionModel.html

A way to quickly test if that’s the problem is to crop the big part of the coordinates from say (1000.014, 1000.015) to (14, 15) and see if the output is different.

That JS library is nice and small, would be great to port.

Still, JTS is a rock solid library that’s been used, worked on and had features added for decades so if you can change your data model to fit with JTS, you’ll get a whole bunch of extra useful features for free like constructive and destructive area geometry which could be a cool addition to your already excellent game idea.

Good luck!

[HappyHydra]

Thanks for helping look into this!

JTS is definitely a huge library with a lot of work put into it. I’m just not sure I can use it yet without a lot of work, but I will play with it some more.

The problem isn’t small angles getting flattened - JTS is creating polygons that intersect. I could take the result and do some post-processing, but I think that may be a lot of work (I haven’t done it before).

I 100% cannot change my data model to work with JTS, since there is nothing special about the data I’m passing to it. It’s just line string data.

The library I mentioned seems small, but it does have some larger dependencies (the red black binary tree library, and also Martinez). I’ve already ported the RBTree and what I need from Martinez, just tidying things up and we’ll see how it compares.

[CommanderKeith]

Hmm, I’m sure there’s some small problem that we’re overlooking.
JTS is definitely made for exactly the use-case you’re working on.
Perhaps I pointed you in the wrong direction to use the nuts-and-bolts JTS, it looks like spatial4j might be the right one since it specifically mentions the types of data it works with:

locationtech/spatial4j

But best check out the whole suite:

LocationTech

I’ve always thought that this map data would make for a great game ever since Pokemon GO came out. I had a zombie style ‘defend your house’ type of game in mind where you can defend your actual house in a top-down shooter style, using google map data. But with family and work I have no spare time now unfortunately.
Cheers,
Keith

[HappyHydra]

I’ll take a look, but so far I don’t see anything about polygon buffering in this library. It seems to be for geospatial queries, which I already use RTrees for.

Technically you can think of this as having nothing to do with geospatial data though. I already do that conversion to world coordinates well, so there isn’t a reason to limit solutions to using those kinds of libraries.

[HappyHydra]

Okay - (almost) done solving this problem! The library and its dependencies have been ported to Java (I never wrote a red-black tree before, let alone really had to use generics, so that was fun).

It’s always fun to see an application grow - while debugging the performance you can see the stack traces are getting quite deep!

First off, sorry about the colors. The roads will be different colors soon, and different types of roads should have different widths.

The only issues I see so far are 1. We spend a lot of time in the RBTree, so maybe I will replace it with a binary heap, and 2. Sometimes there is an infinite loop preventing anything from rendering. But, progress.

The library works really well, handling complex shapes:

You can see here I hadn’t moved water ways (purple) to the new library yet. It’s still on JTS’s OffsetBuilder, and we can see how it messes up on one of the segments:

Here it is fully on the new library.

Next is to fix that infinite loop and a little optimization (at least trying a binary heap instead of the tree, or a different type of tree).