• System 'economy caching' ported & re-worked from old code; helps AI agents reason about job and market availability within a system or zone
• High-level AI reasoning; forms the basis of AI players' ability to dynamically choose a profession based on profitability analysis
• Basic colony population dynamics (helps create a time-varying economic sink/demand for basic goods, thus seeding the system economy)
• Market mechanics now fully-implemented including escrow, on-station/on-colony storage lockers for temporary storage of bought goods or canceled sell orders, etc etc.
• Limited implementation of Zones -- already in-use by AI for reasoning about job locations, but no zone gameplay mechanics (ownership, laws, etc.) yet
• Happened upon a new algorithm for individual asteroid/ice/debris/whatever placement within fields, resulting in much more natural looking fields (no longer are they obviously ellipsoids )

• A boatload of UI polish and new features.
• A cleanup pass on the engine.
• Completely overhauled the way we generate engine bindings for Lua.
• Reorganized and simplified our Lua support code.
• Implemented the 'control bar' for switching between e.g. ship control, command view, etc.
• Refactored camera control to allow smooth transitions between different cameras.
• Re-implemented the command view.
• Designed zone control mecahnics.

Spoiler:      SHOW

Spoiler:      SHOW

Spoiler:      SHOW

Input
Update
Layout
Draw

Spoiler:      SHOW

Chris Martin wrote:Oh but if you never try, you'll never know
Just what you're worth

JoshParnell wrote: ↑

Fri Jul 13, 2018 8:11 pm

Hail, spacefarers!

In today's log, I'm going to afford myself a mental break from talking about the economy again and instead walk you through how to build a universe with interesting structure, which is something that I have been doing recently to take a breather from pricing, economy, credits...it was all starting to drive me a little mad. I spent roughly another two weeks on it all, then decided that I really needed to dip my toes into something else before I started having nightmares about market orders. That being said, I was still thirsting to do something with a 'big picture' feel to it, since I have spent so much time on little pictures, hence this excursion into universe generation! It was a fun process, so I will share it in enough detail that you should be able to build your own universes if you so desire

Starting with Star Soup

Let's jump right in. For our purposes, building a universe consists, essentially, of building a graph (a collection of vertices and edges linking those vertices). Vertices represent systems, edges represent wormhole or jump gate connections between systems.

The most basic starting point is a random collection of vertices, distributed uniformly over a space. This is as boring as boring can get:



Still, we have to start somewhere...

Getting Connected with Kruskal's

If a uniformly-random distribution of points is the most basic way to generate vertices, then the most basic (sensible) way to generate edges is via a technique called the minimum spanning tree. For our purposes, what it means is that we want to 'connect the dots' in such a way that we are using as little 'distance' as possible. In other words, we want to make it possible to navigate from any system to any other system, but we also want to make the connectivity such that nearby systems are the most likely candidates for being connected. When you see it, you'll understand why we want to connect our systems like this

Luckily it's easy to write the algorithm for doing this! There are two great, easy choices: Kruskal's and Prim's. Since the former is slightly more general and I have written it many times before, I will use Kruskal's. They produce the same results when building a single MST.

Here is our soup of stars, this time connected with the MST:



Already looking better!

Notice how the connections are made in a very 'orderly' way. That's because of the MST. Connecting random stars will yield a far less attractive map.

Hierarchical Detail: Regions & Regional Substructure

Clearly, this universe is too boring. We would like to see more structure: stars within clusters within regions, etc. 'Real' physics aside, structure will make for far more interesting gameplay, and a better feeling of getting to explore an interesting universe.

Here's an idea: what if, instead of generating a bunch of uniform stars in a soup, we were to generate a few regions in a soup, then start 'attaching' stars to those regions? Let's try it. We'll generate 20 regions, then 1000 stars, each randomly attached to a region and with a 5% random exponential deviation from the regional center. Then we'll connect it all just like before.

The results are much more encouraging:



Note that I have given each region a random color here, and stars inherit their region's color, purely for the sake of being able to see the regions on this map. We will obviously draw this whole thing in a prettier way for the in-game UI

There are lots of ways we can tune the generating parameters to change the structure. For example, while I like the rather chaotic nature of these regions, you can change the system position-within-region distribution to gaussian instead of exponential to 'tighten up' the regional clustering. Here is what gaussian with 0.7% deviation looks like, using the same seed as above:



And, just for show, 50 regions with 2000 systems (back to exponential distribution):



(Yes, I too wish the colors were prettier...but remember...no getting distracted by...graphics...... )

Generating Shortcuts

At this point, things are looking quite nice. However, if you look carefully at the map and think about navigating around these systems, you may find that it seems quite tedious! Indeed, getting out of a distant 'corner' of space can take a lot of jumps. This is, in fact, by design! The minimum spanning tree is exactly that: it uses the least amount of 'connective line' that we could possibly use to make a connected universe. In particular, there is zero redundancy. Since it's a tree, there is also exactly one (non-overlapping) path from any point A to any other point B, never more. It's an efficient universe in terms of wormhole usage, but it's not very kind to the weary inter-regional merchant!

Looking at these maps, you can probably see 'obvious' places where you could draw an extra connection or two and really cut down on the amount of travel required to get around. For example, here's an annotated map where I've drawn in some obvious choices for extra connections that'd make things easier:



We'd like to generate such 'shortcuts' automatically. But how? Teaching the computer to identify good shortcuts is actually not so easy. We need a way to mathematically define good shortcuts. Intuitively, we want to choose two systems that are topologically far apart (that is, the path between them is very long), but are physically close. You will indeed note that this is a characteristic of all the sample shortcuts I drew above: they bridge systems that are physically close to one-another, but very very far apart in terms of the 'path length' between them.

So, all we have to do, for each shortcut we want to make, is: find the pair of systems whose ratio of travel distance to physical distance is the highest, and connect them. Turns out, this algorithm works really well for the most part. (Note: in reality, I use travel distance divided by the square root of physical distance, which encourages the algorithm to think more globally rather than making intra-regional shortcuts). Here are the first three shortcuts that the algorithm selects on the above map:



Hey! Look at that! Two of the three shortcuts the computer chose made appearances in my annotations (I swear I did not check before I annotated!) Sadly the algorithm did not come up with a space whale option, but it would be difficult to teach the computer to be as silly as me. We'll check out one more example, this time with 5 shortcuts:



I really like these choices

The shortcutting algorithm serves to make the map's structure even more interesting, since we now have more options for getting around, but we have introduced those options in a very specific way based on our goal of providing the most 'bang for our buck' with each shortcut.

Unfortunately, this shortcut algorithm is also computationally expensive. Computing all path lengths on a graph is expensive, and doing so in an efficient way is a significantly harder algorithmic challenge than computing the MST. I've played with a few cheaper ways of computing shortcuts, but none have come up with as good of results. I'm sure that, with a bit more thought and cleverness we could solve this much more quickly. For now, I'm pleased with the results, and will optimize more as I am able.

(Bonus) 3D

It should come as no surprise that all of the algorithms I've discussed extend effortlessly into 3D. In fact, while building the generator, I used 3D math the whole time, but kept a configurable constant that let me collapse the third dimension at will.



For Limit Theory, I have expressed that I will likely default to 2D universe maps; I prefer the simplicity. However, as demonstrated, it's effortless to enable 3D generation, so we can include that as a configuration option in the universe generator

(Bonus) Making it Infinite with Boundary Stitching

But wait! Limit Theory advertises an 'infinite' universe! So far we have only seen finite ones. What's the deal? The deal is quite simple, in fact. To make a universe infinite, all you need to do is 'tile' a finite one -- that is, use your 'finite universe' generator to generate content for each 'cell' of the universe, then find a way to stitch them together. Think of these screenshots we have seen so far as single 'pixels' in the infinite picture of the universe. The only interesting problem with this approach is how to connect the cells. In particular, if we want to make sure that the universe actually does go on forever (and that we can actually get to new systems forever), then we must make sure that the entire grid is connected.

The way to do this is very easy: choose a star system to represent each border of your tile (in our case, for a 2D grid tiling, we could call them N, E, S, W, for example), then connect the borders of adjacent tiles appropriately (the N border-system of a tile will be connected to the S border-system of the tile above it, etc.) To choose which systems should be border systems, there's an obvious answer: the system that is closest to the border (duh?) In other words, the northmost system in a tile will be our N border. To make all this clear visually, we can draw our border systems on the map and extend lines outward to indicate where our universe tile will be stitched to neighboring tiles:



So, when the player is getting to within topological proximity of one of those four border systems, we need to ensure that the appropriate adjacent tile in the universe is generated (and receives enough historical simulation to 'smooth out' border effects). The generator automatically identifies the border systems and flags them as such so that the engine will be able to handle preloading accordingly.

I have actually decided, over the course of LT development, that I don't want to play in an infinite universe, but would rather have a large, finite one (so that I am forced to get to 'know' it, rather than endlessly skipping town to the next cell). That being said, infinite universe generation is clearly one of the promises of LT, so I fully intend to support this tiling / stitching system despite my own preference to play without it (finite/infinite will be yet another universe configuration option).

By the way, in case it isn't clear, one very important property of the border stitching mechanism is that you don't have to generate the neighboring cell to know how it is connected to your current cell. This is in stark contrast to how we generated the finite universes above (we can't find the MST of an infinite graph, for obvious reasons!) This is the fundamental trade-off of infinite generation: you must have some topological regularity at some level. But, you see, we can play this clever trick of making each 'tile' of our regular grid a rather complex structure in its own right, which ensures that we get a much more interesting universe than if each cell in the grid corresponded to only one system.

(Update) Improving Local Connectivity

See this post for a simple technique to improve the local connectivity, which, as some have pointed out, is really too low with just the MST.

---

Alrighty, that took me a little too long to write, no surprises there, but you guys were patient to wait for it...so thank you

I will be getting back to my global economy work soon, but this multi-system work is also quite exciting, so I'm going to keep at it for a bit longer. I wanted to have a few more features like region names & system properties done for today, but I spent my time on the shortcut algorithm and the spatial faulting algorithm (which I cut from this devlog due to results not being that interesting) instead. Ah well! Perhaps next time

Hope you all have a great Friday!

AdamByrd wrote: ↑

Fri Jul 20, 2018 12:50 pm

Friends. Compatriots. Limit Theoreticians. I come bearing a dev log.

As always, I've been bouncing around like a madman. Sprinkling a little feature dust here, vacuuming a few bugs there, reinforcing scaffolding, ensuring the house stays tidy as we scale, etc etc. Oh, and I may have finished an entire engine system along the way. First up, Docking!

---

Docking
Last time I showed off the command interface. A large part of that was ensuring we can switch between 'contexts' smoothly. UI gets swapped out, the camera animates, bindings are changed out, and so on. These are small things that are going to be leveraged frequently. After finishing the command interface I wanted to continue working on gameplay and also push on these features a little more to see how they hold up. Docking seemed like a good fit.

We wanted to start with just the core mechanics: fly close to a space station, press a button, auto-pilot to the docking port, and see UI menus for everything you can do at that station.

First, a dockable component. The UI simply searches for dockables and if you're in range presents a button prompt to begin docking. The act of docking actually removes the player's ship from the world and adds it to the station instead. Similarly, once docked an undock prompt is presented.

I extended the MasterControl I implemented last time to add 'control sets'. The UI looks at the player each frame to determine which control set ought to be active and automatically switches to it. Previously we could choose from piloting, commanding, and debug controls. Now, when the player is docked we swap to a control set with things like your storage locker, merchants, and the jobs board. Since we can already swap out UI trees easily this ended up being dead simple to implement.

With all the state control in place, I wanted to make it a smooth, physical docking operation where you literally fly into the station. The AI is implemented through an action stack. Actions are pushed onto the stack and AI simply run their current action each frame, popping them once complete. Conveniently, the player is no different. The action stack is just empty and the UI controls poke the player's state directly. (This actually surprised me when I built the command interface because I could select my own ship along with my allies when giving orders and my own ship would fly along, taking part like any other unit.) I added a new docking action that is essentially the 'move to location' action that also happens to reparent the player from the system to the station once at the destination. And boom, with a whopping 7 lines of code you now auto-pilot right on in.

If a station is destroyed a fraction of the damage is inflicted on docked entities and they're released from the station. If your ship survives the damage, great, you can limp away. If not, well, your attacker gets to rummage through the debris of your ship along with the station.

It's not a particularly big or complicated feature, but I'm thoroughly pleased with how brain-dead easy it was to implement. The way Josh structured AI and actions is excellent. There's a ton of power and flexibility there with no real complexity. The whole of implementing docking took a day, with about 3 hours being the 'real work' and the rest polish and iteration.


Physics
We've been putting off physics work for a while now. We had kinematics, parenting, a naive broadphase, and sphere-vs-sphere narrowphase, and naive raycasting, but we still needed a lot more work. The broadphase failed spectacularly at large vs small object checking, raycasting needed to be accelerated through the broadphase spatial grid, and we wanted more shapes (convex hulls and boxes) and numerical robustness. We also didn't have a way to actually respond to collisions outside of kinematics (for sparks, sound effects, damage, etc). None of that is particularly scary, but the sheer amount of work still needed was.

Josh decided we should investigate off-the-shelf physics engines and decide which path would strike the right balance of development time and quality. So I took some time to evaluate our options. The 3 most well known being Havok, PhysX and Bullet. Honestly, I don't like the way most Havok demos look and feel. The licensing for PhysX is messy and I'm just kind of assuming it's a behemoth. In all the comparisons I've looked at Bullet seems to be the most consistent. It's rarely the absolute best in terms of performance or simulation quality, but it's very consistently #2 and right on the heels of #1. Physics and Havok on the other hand are excellent in some situations and abysmal in others. The consistency of Bullet is extremely appealing to me.

So I decided to integrate the bare minimum amount functionality leveraging Bullet that would let us see it in action. That would let us gauge the quality in our own use case and the time/difficulty associated with using it. I decided to do this as an entirely separate physics API in the engine that mirrored the existing one but didn't replace it. This let us actually toggle back and forth between new physics and old physics with a single variable. This was fantastic for comparing the two. We were able to ensure that everything felt exactly the same in both engines. This meant we wouldn't have to re-tune ship controls if we did end up swapping out the physics and also highlighted anywhere our current physics implementation was doing things incorrectly. Luckily, nearly everything matched up easily: drag, restitution, friction, etc. However, our inertia was pretty far from accurate. This worried me since it made ships feel completely different. In the end I was able to fix the inertia calculation in the old physics and updating the forces and torques could be done analytically to keep the same feel.

Once everything was set up correctly Bullet ended up feeling identical. Implementing it wasn't particularly difficult, it has all the features we want, and it's reasonably performant. It looked like it would be faster to switch to Bullet and we were confident it would yield very acceptable results. I set out to officially migrate us over and to flesh out the rest of the physics API we need to finish the game.

Unfortunately, nothing is ever easy and I it wasn't long before I started finding Bullet's rough edges, quirks, and flaws. Constraints are unusably slow, compound objects and triggers have awful API, I found a couple outright bugs, memory allocation is a mess, and the documentation is a half step above worthless.

Still, with enough hammering, it works. We have all the features we were aiming for and the implementation isn't a complete disaster. Some of the new stuff we now have is shapecasting, overlap tests, triggers, collision groups and masks, convex hulls and box shapes, and per-system physics. It may have taken 5 weeks, but it's done now and it shouldn't need any major changes going forward.

Overall, it's a win and I think it was the right choice. However, in the future I would likely avoid Bullet. In a professional setting I'd go with PhysX and see if it fares better. On hobby stuff I'd suck it up and write my own. The real kicker though, is that Bullet isn't awful. The author has done some quality work and I'm happy Bullet exists, it just the API design that's a disaster. All it needs is about a month of someone with API design chops hammering on it and it would go from irritating to a joy to use.


Math
Along the way, something happened that brings me great joy. I finally fixed all the math in the engine! This has been sitting in the back of my brain driving my nuts for months now. I probably first realized we had serious issues back in December. It's one of those things the tends to show up at unexpected times when you're in the middle of some other task and fixing it is going to break a ton of other things and you don't even know where it's broken and no one knows how quaternions even work and it's going to take forever and you just want to finish this one task and...you get the idea. It continually gets pushed to the back burner.

When I ran into it again with the camera work in the last update I told Josh that the next time it comes up one of us is going to suck it up and fix it. And by 'one of us' I mean me because Josh hates quaternion and matrix code.

Well, when I was integrating Bullet I ran right back into these math issues almost immediately. When rendering we have to get the position and rotation of objects out of the physics engine. Bullet has a lovely function that fills a matrix in an OpenGL format. But our matrices were in some weird, partially transposed state due to our bugs so we couldn't even use that matrix without first doing some obscene hacks to get it to match our format.

I mentally prepared myself for a good 5 days of anguish digging through our math and tracking down every last issue. I spent a couple hours cataloging all known issues and our coordinate system conventions in every part of the rendering pipeline. In the end, the majority of our issues traced back to Matrix_GetRight/Up/Forward and Quat_GetRight/Up/Forward. Turns out almost all of the math was 'correct' except when we converted from axes to actual on-screen directions. Both sets of functions were wrong and wrong in different ways. This is what made it tricky. Once I realized that I simplified a bunch of our math and found a few other small mistakes and remove all the ugly hacks we had before. The tests I wrote last time were a tremendous help. In the end, I only spent a day on it. Victory.

---

The End.
And now we get to the sad part. This will be my final dev log. My journey with the awesomeness that is Limit Theory is at an end.

From the very beginning Josh and I discussed a finite end. My job was to help clear the last major hurdles and open up the path for Josh to grind away on gameplay. To that end, I think this has been highly successful. The hope was that we'd be able to ship during that time frame, but alas, we didn't make it.

My plan for the last few years has been to move to the west coast, maybe Seattle, and find work with a stable indie studio. As luck would have it, something decided to fall directly into my lap. Shortly before GDC, Blizzard reached out to me and, long story short, I'm joining their new shared engine team at the beginning of August.

I leaned away from working for a AAA studio because I was scared of the potential soul-sucky nature of it, but once I actually visited Blizzard, that changed. I've gotta say, they've built an amazing culture there. Everyone I spoke with was happier and more creatively empowered than almost every indie studio I've seen. And I can bring Tess to work.

For the past month I've been working part time, winding down. I'm happy I managed to get Bullet fully integrated before I leave. I'm incredibly proud of the work I've done here, and extremely grateful I've gotten to work alongside an awesome programmer and person like Josh. I've grown tremendously as a programmer in my time here, and I certainly wouldn't be in the situation I am if it hadn't been for Procedural Reality. It's been a fantastic 14 months.

It's bittersweet, as endings tend to be. I'll miss the insanely creative and detailed discussions and the uniquely welcoming and cerebral community you've all built. I'm also excited beyond words about what comes next.

Cheers,
Adam

JoshParnell wrote: ↑

Sat Aug 11, 2018 6:54 pm

Well, I hate doing this, but: I need another week.

My recent work has consisted of moving a major game subsystem from Lua to C, which is an ongoing process as you all know. In doing so, I had to choose between one of two major, high-level architectures, each with very different strengths and weaknesses. Despite having high hopes in the beginning, after having the system solidly in-place, I have only just come to the conclusion that I made the wrong choice. Sadly, it was necessary to have the system up-and-running before I could make the determination that it wouldn't pan out. It's rather heartbreaking, and, while I had planned on simply writing an account of this (failed) work, I feel that my time would be better spent taking the weekend to recharge, implementing the system in the other architectural style next week, and writing about the results at that time. Frankly, I'm too disgruntled and exhausted from work to produce a decent devlog at the moment anyway.

Apologies! If lessons learned the hard way are a currency, then I am a very rich man On the brighter side, I'm sure it will make for a compelling story. Just...not right now

Hyperion wrote: ↑

Sat Aug 11, 2018 6:59 pm

Another week? Unacceptable! I demand an 8000 word log within the next 15 minutes!

Well could you at least say what system it is, and could we get a shiny or 2 to hold us over? You could say work on graphics for an hour or 2 tonight and still technically deliver something today Might help alleviate the heartbreak too

g = GUI.Canvas()
g.add(GUI.Window("Universe Configuration")
  .add(GUI.Checkbox("Infinite Mode").bindTo(&config.infinite))
  .add(GUI.Slider("Average Systems Per Region", 10, 1000).bindTo(&config.regionSize))
  .add(GUI.Slider("Average System Connectivity", 1, 10).bindTo(&config.connectivity))
  .add(GUI.GroupHorizontal()
    .add(GUI.Button("Create", createUniverse))
    .add(GUI.Button("Cancel", cancelUniverse))
  )
)

...

g.update()
g.draw()

GUI.BeginWindow("Universe Configuration")
  GUI.Checkbox("Infinite Mode", config.infinite)
  GUI.Slider("Average Systems Per Region", 10, 1000, config.regionSize)
  GUI.Slider("Average System Connectivity", 1, 10, config.connectivity)
  GUI.BeginGroupHorizontal()
    if (GUI.Button("Create")) createUniverse()
    if (GUI.Button("Cancel")) cancelUniverse()
  GUI.EndGroup()
GUI.EndWindow()

• UI code is extremely concise, easy-to-understand, and quick to write
• The UI does not need any 'extra information' -- sliders/checkboxes/radio groups don't need pointers to the data they represent, buttons don't need callbacks for the actions they trigger
• Changing data never requires special logic to inform the UI about changes, making it effortless to build UI for dynamic data that changes frequently (like game data!)
• Easy to use from scripts; no special binding code necessary

• Automatic layout is heavily-restricted
• 1-frame delays are common and sometimes unavoidable; can result in 'popping' and added input latency
• Higher CPU usage

• Automatic layouts are easy and can be made arbitrarily-complex
• No frame delays, minimal input latency
• Minimal CPU usage (predicated, of course, on a well-optimized implementation)

• UI code is often verbose
• UI must have knowledge about the data it is displaying and must understand how to trigger functionality -- pointers and callback mechanisms are typical
• Users must take special care to ensure the UI stays in-sync with data -- complex, frequently-changing data requires significant consideration to work properly
• Usage from scripts requires special consideration; UI must know how to access script data & functions