next »

[Ashkin]

Pretty cool! The leve generation's good right now, but I think it could use some tweaking- maybe pregenerate streets that cut through the city or something at a certain level, and have some buildings that are slightly bigger.

[Danmark]

Sorry for the lack of updates. Made no progress for 3 weeks, while a good friend from overseas was visiting. Been regaining momentum lately. Clicky:

Shown in the video is a demonstration of the dynamic portion of the propagation system thus far. Green tiles are ones that are still sending off potential players to other tiles, while red ones have finished doing so.

It's sort of like a cellular automaton. Here's how it works in detail:

There's an entry for each tile with its current state (not yet reached, just reached, propagating, finished propagating), a time in milliseconds representing how long the player could've been at the tile for, and an index. The time is only pertinent in the reached and propagating states.

A propagation instance, which is for knowing possible player positions at either a hypothetical future or the actual present & contains the entries discussed above, can be advanced by a given number of milliseconds. When advanced, all propagating tiles add the advanced-by ms to their time, then look at their respective time-to-tile lists in the static part of the system (see the last big post). Any time-to-tile which is less than or equal to the source tile's time becomes a reached destination tile (if it's not already propagating or finished). A recached tile's time is initialized to the source tile's time minus the time-to-tile, so that it properly represents how long the player could've been there. If a tile is reached by multiple tiles in the same advancement, it always takes on the highest time, to ensure it's reached as soon as possible (via the fastest route).

The source tile stops looking for new destination tiles once it encounters a time-to-tile that's greater than its own time (yet to be reached), and records this point in the index field of the entry, where it picks up from on the next advancement.

In a second pass, all reached tiles become propagating ones. One thing to note is that propagation states aren't strictly correct, because a tile could be reached and have enough time left to reach other tiles itself within the same advancement (which occurs over an arbitrary time step). However, as long as the time steps are kept modest, it's self-correcting. A tile that propagates late has more time, time which continues to propagates through the system each iteration.

That's all for today. In spite of my previous enthusiasm, making the dynamic propogation stuff properly take enemy visibility into account is turning out to be rather complex.

Pretty cool! The leve generation's good right now, but I think it could use some tweaking- maybe pregenerate streets that cut through the city or something at a certain level, and have some buildings that are slightly bigger.

It's promising that you like the level generation, since it's 7 lines of piss-simple code. Just needed something that made interesting enough shapes to test the various systems. Haven't really worked on that part yet.

Thanks for the suggestions!

[Belimoth]

This devlog is full of things that I like.

[Danmark]

Red herring bug screenshot:

Blown the propagation-with-enemies issue wide open. With any luck, I can show a video of enemies interacting with player propagation tomorrow.


As an aside, here's something possibly interesting to aspiring and actual programmers I snipped out of the last devlog for brevity's sake:


Had a bit of a revelation about storing information per tile. As explained in previous posts, I've used dictionaries (implemented via hash tables in .NET) mapping tile coordinates to per-tile information. What I realized is that each tile can be given a unique index out of a contiguous range, so that per-tile information can be stored simply as lists, with the pertinent tile implicitly defined by the info's position in the list. No more dictionaries. Also, lists of tiles can be represented as tile indices, which are more compact than coordinates. One consideration is how easily copyable a dynamic propagation state is, because the AI will need to copy them hundreds of times per enemy as it works out a plan. Compactness is very desirable. Finally, many parts of the code can be simplified due to handling indices instead of coordinates.

Either an index or set of coordinates are sufficient to define a tile. The new scheme can convert between the two in constant-time, and with reasonable locality of reference. Converting from index to coordinates just takes the entry at that index from an array of all tile coordinates. That's all there is to the index->coordinates structure, but it's a bit weighty at (maximally) 12 MB. I can get it down to 3 MB with little difficulty. In any case, the idea is to use indices rather than coordinates whereever possible, which is almost everywhere.

Converting from coordinates to index is a bit more involved. For each ground tile, certain things are stored. These are the ground tile's height, the base index of it and its associated walls, and an “array” of cumulative counts of the heights of its walls, like this: North wall, North+East walls, North+East+South walls, North+East+South+West walls, North+East+South+West walls + 1 (for the ground). These define the indices, relative to the base index, of the North wall, East wall, South wall, West wall, and ground, respectively. Within a wall, the index is found by subtracting the difference of the height provided in the coordinates & the ground tile's height (this also works for the ground tile, because the difference is always 0). So a tile's index is given by the base index + wall/ground index + within wall difference. The entire coordinates->index structure takes up exactly 16 kB for my 64*64 ground tile worlds.

Neither conversion involves branching, except whatever's imposed by .NET.

[Danmark]

Despite appearances, not a poor man's city simulation game:

Is it linking you to the video at 720p for you guys? YouTube's refusing to do so on my end. Tried putting it on Hipstertube instead, but there's a 500MB limit there.



Making propagation take enemy visibility into account proved a challenge. Why is it a problem? For efficiency and simplicity, tiles never propagate more than they need to. They do so to each excident connection exactly once (see the last big post). In this way, only the boundary between where the player can and cannot be is processed.

Trouble is, that boundary changes depending on where enemies can see. Player movement is constrained by enemy visibility. Notice in the video that the region potentially containing the player is shaped by enemy positions. If an enemy searches some areas, then leaves them, a bunch of tiles left are left behind that will possibly contain the player at some point in the future. But in the propagation system's previous naivate, those tiles would be considered empty forever afterwards. Enemies would cut swathes through the world, eventually making the absurd reckoning that the player can be literally nowhere.

The solution is reverse propagation to augment the forward one. Ordinarily tiles give hypothetical players, but tiles in the reverse state take them by checking every incident connection. As soon as one can reach it in time, it enters the ordinary forward propagate state. Whenever tiles become invisible to enemies, they enter the reverse propagate state. Enemies thus leave behind trails of reverse tiles in their wakes. The player can obviously enter areas already searched by enemies, a fact accounted for by this reverse stuff.

So that incident connections/"who can reach me and when" for each tile can be accessed efficiently, there's a second lot of precomputed propagation data, of exactly the same size and form as the one discussed in this post. I generate it quickly from that pre-existing excident connections/"who can I reach and when" data, in code that feels a bit like a counting sort.

Reverse propagate tiles show up (ever fleetingly) in blue in the video. It's curious that they look so insignificant in action, yet without them, the whole system would break down. The ultimate you missed a spot.

In fact, reverse propagation would suffice for all my needs. It's just ten times slower, and as it turns out, I need all the performance I can get. Next I need to make hypothetical propagation states work on a small part of the world; the area which an enemy can potentially affect during the future period he's thinking about. Otherwise it won't be fast enough to make any decent AI.

[Danmark]

Project's not dead. I've been working on AI:

The gist of the AI is that each frame only runs AI for one NPC, and there are two (implicit) states oer NPC: search for player, and go to player's last known location. Today I'll discuss what's become of the former- the only state that uses all this visibility and propagation stuff. Boring pointless history follows, skip to the horizontal rule down there if you have any sense.

It turned out that propagation wasn't going to be fast enough for me to implement the behavior I'd wanted originally. Now, a propagation instance is basically a time field, annoting per-tile how long the player could've been there. The idea was for each NPC to consider a bunch of paths, and for it to pick the path that minimizes the amount of time the player could be anywhere- to minimize the sum of time across the environment. This corresponds (roughly) to the goal "cut off as much of the player's possible movement as possible". It'd require propagation to be run at each path fork (2^8=1024 times), which wasn't gonna happen, even if I implemented local propagation like I said I would.

So I dumbed it down. NPCs still thought ahead to the future, but only accounting for the way fellow NPCs constrain player movement, not themselves, and simply "gathered up" as much time from the field as they could. This is (roughly) "search the areas that haven't been searched in the longest amount of time" and "cut off some player movement". This required propagation to be run a small number of times (8, corresponding to the number of moves into the future NPCs consider). It worked quite well. Gave the impression the enemies were seeking out the player.

But it was still too slow. Wanted to spread out the propagation over a few frames per NPC, which would've been doable if each propagation calculation took a consistently low amount of time (it varies by about 4x). Otherwise, I'd need to spread over more frames, which sacrifices responsiveness of AI for performance (recall that only one NPC is 'thinking' per frame). Problem is, responsiveness would've been abysmal.

Realizing that the biggest thing thinking ahead did was allow NPCs to enter the search for player state earlier (more on that next update), which was good but not worth the performance hit, I dumbed it down again. Now, the abstract goals are the same (see above), but NPCs only take into account how long the player could be at places right now. To ensure NPCs search different areas, which was handled more explicitly through propagation before, I just give tiles the thinking NPC knows his comrades will search in the timeframe of the plan he's formulating a utility of 0.

Results aren't quite as good, but they'll suffice for now. Still plenty of room for improvement. It's not worth more of that until I get the procedural generation working, so I can get more meaningful results from playing against these NPCs- though I've already discovered serious gameplay/AI issues including:

• Enemies can't patrol enough of the world no matter how well they patrol- it takes zero effort to avoid them.
• When the player is spotted, there's a brief challenge in escaping the enclosing enemies, after which he has impunity*.
• After the player has escaped, it takes too long for enemies to disperse throughout the level again.

To solve #2, right now I'm thinking teleporters that only enemies can use, so they can keep putting pressure on from multiple directions. Due to the way everything works already, this should be fairly easy to integrate.

#3 is simple enough. There's a clear point where they've lost the player altogether, at which time I can force them to spread out.
#1, not sure about this. Within reason, I can crowd levels with a few more enemies, though I think that'll never be adequate. Perhaps this entails a shift in focus of the game.

Please check out the new demo. Tell me what you think, bearing in mind you can't play anything interesting lest you get spotted, and that I didn't bother stripping out all debug stuff (only use WSAD & space to avoid weirdness). Until next time, friends, and may it not be 3 months ahead!


*insert thumb idiom here

[Danmark]

Everything I've read about random city generation has either focused on visuals alone, or has emphasized 'realistic' cities. My requirements are techniques that create a world conducive to Sneaky's gameplay, and that gives the impression of a city. One big difference is my worlds don't have centers, unlike real cities. So I decided to go alone & try out some of the simplest techniques I could think of.

Streets
There are two kinds of streets: avenues and roads. Avenues are very neatly arranged, wide streets. Roads are more disordered, narrow streets.

Avenues are generated first, on a map downscaled by 4 times on both axes, to ensure a width of 2 with a relief of at least 2 between different avenues. A bunch of 4-way intersections and corners are randomly created on the smaller map, and each of their 4/2 avenues that meet at the intersections/corners respectively are extruded until they hit another avenue (thus creating 3-way intersections). It's all done iteratively: every ave pushes out 1 space every step.

Next are roads. Roads are carved out by 'walkers' that tend to walk forward, but may turn left or right each iteration. For the latter part, I needed a probability distribution to sample (in the past I've used trivial ad-hoc monotonically decreasing distributions, which are inadequate here), a source of some analysis paralysis until I discovered the elegant triangular distribution. I strongly recommend it: it's so easy to implement & use compared to 'smooth' distibutions like normal and logistic. Anyway, roads are created iteratively, like avenues. You can see the weird labyrinthine patterns randomly placed walkers create below.

This was far too chaotic, so I added a rule to walkers that they halt if carving the tile ahead would lead to an area of 2x2 being carved. Note this is sufficient to prohibit any areas larger than this as well. Then I added some higher-level structure, the avenues discussed above. I made it so walkers are always placed along avenues: this ensures a true street network, where every street is connected to every other. Before that, there were lots of islands. Putting it all together, a street network looks like:

Buildings
Second phase of city generation is buildings. I didn't wanna use any well-known noise techniques, because they didn't seem pertinent. My buildings are restricted in height to 6 units, and for generation, there's only a range of 5 to work with, since a building is at least 1 unit high by definition. Plus, I wanted it possible for regions of short buildings to border ones of tall buildings. So I created an algorithm based around buckets rather than continuous height.

There's a working set of tiles, to which every tile to become a building is added. There are 3 buckets: short, medium, and high. There's also a 'spreader' per tile, which stores how many hits that tile has taken in each bucket, along with how many hits in total. When a tile is selected from the working set, its spreader determines which bucket the tile falls into, where the chance of each bucket is the bucket hits over total hits (if no hits, we go back & select a different tile). With the bucket determined, the spreader spreads to all other spreaders within a certain (Chebyshev) distance by hitting them in the same bucket. Hits are attenuated linearly away from the spreading spreader. Finally, the tile is assigned its bucket & removed from the working set.

The idea is a building of one height in one place increases the probability of nearby buildings being the same height.

The working set is initialized to every tile not a street. This makes buildings far more coherent w.r.t. the blocks they're in, as streets can't thus contribute hits, and are barriers of sorts. Next the algorithm is kicked off by processing some tiles with buckets assigned a-priori. From then on, the algorithm continues until the working set is empty. Perhaps a mathemagician could tell me what kind of noise I've bastardized with this technique. This is what it looks like sans roads & the last step:

Transforming bucketed tiles to heights after all this is trivial. Short ones are 1-2 units, medium 3-4, and high 5-6. Each bucket has a probability tiles in that bucket will hit the ceiling.

City generation is passed 12 explicit parameters, which is reasonable (2 for avenues, 3 for roads, 7 for buildings). Still haven't played much with these- that'll have to wait until I have an in-game GUI for world creation, which is my next task. It's all fast enough, taking only a couple seconds in debug mode. Considering the pre-computation for AI is 10+ times that, it's not likely I'll be optimizing this stuff.

I notice cities are less readable than they were with the super naive world generation. Plus I'm getting sick of looking at this thing. Definitely time to get some textures in.

[Ashkin]

Amazing! I didn't understand half of that, but the generation is looking great- though I think something is lost between the one-block tall buildings with streets and the final product.

[Kurt]

I'm sure this'll sound dumb if that, but have you consider have "sewers"? Just a few holes that lead to another z-level of blocks with a labyrinth type structure.

[Danmark]

Amazing! I didn't understand half of that, but the generation is looking great- though I think something is lost between the one-block tall buildings with streets and the final product.

Thanks man! FWIW your proc gen in Subterrane seems more sophisticated, so I'm probably just not good at explaining technical things (part of the reason why I'm practicing with my tl;dr posts).

You're right about something being lost between road networks and full buildings, but I reckon that's the readability issue with (a lack of) texturing I mentioned. Inspired by your post, I resumed work on textures and made a video:

Lemme know if the roadness of roads has improved (need to redo their texture as their Cairo Pentagon pattern's too small).

Still a good ways to go with texturing. I want at least 2 wall tones, and more directed roofs. And doors. Was gonna have way more varied windows (there are 3 now) but the patterns on them get lost as it is, so meh. Decided on 128^2 textures empirically based on running in 1920*1080 a while ago, but in retrospect, 64^2 would've been more appropriate. Nothing is lost. Still ought to make special ground floor windows.

Very much a novice at texturing. What surprises me is that bigger noisy textures are easier to make than smaller pure pattern textures. Anyway, the latter is what I'm sticking with for Sneaky. Experimented with noise but decided textures are always too small in screen space for noise to pull its weight, and I think the clean aesthetic suits the game.

Also I've decided in favor of adornments (air conditioners, drainage pipes, power lines, etc.) after all, but I'm not sure about how to make them not impede movement in a concise way. There needs to be thousands at once. They could fall & be destroyed upon being hit, or simply be passed through, or whatever. In any case, the player needs to know not to bother avoiding them. How best to go about this?

I'm sure this'll sound dumb if that, but have you consider have "sewers"? Just a few holes that lead to another z-level of blocks with a labyrinth type structure.

I'd considered tunnels but decided against them. It'd take some serious shuffling of the already complex (but not massive) code, and wouldn't play nicely with the stereographic projection. What purpose did you have in mind? Perhaps it could be accomplished another way.

Anyway, not a dumb suggestion, but I'd be dumb to follow it. Can't afford to expand this project's scope.

[Ashkin]

Shucks. Thanks, but Subterrane's gen stuff isn't very sophisticated at all. I think the buildings might be more 'coherent' if you raised levels in chunks of more than one block somehow- that way you don't have those one-block gaps here and there. Also maybe have it so, except on very rare occasions, the levels always go up as they approach the building's center?
As for the decorations, I'd say make it so you can pass through them, but make sure there are none wider than the player so it looks like he's always climbing over them rather than having them pass through him.

[Playaction]

Wow - those textures really made a difference. I like the clean cartoony look of the textures combined with the wide-angle-lens-y effect of the camera.
Good job!

[Lynx]

This is looking interesting, but the taller buildings obscure any paths (and potentially enemies) behind them.  It'd make a really nifty god game perspective though, I could picture a game about ruling over a tiny city-covered asteroid!

[Danmark]

Shucks. Thanks, but Subterrane's gen stuff isn't very sophisticated at all. I think the buildings might be more 'coherent' if you raised levels in chunks of more than one block somehow- that way you don't have those one-block gaps here and there. Also maybe have it so, except on very rare occasions, the levels always go up as they approach the building's center?
As for the decorations, I'd say make it so you can pass through them, but make sure there are none wider than the player so it looks like he's always climbing over them rather than having them pass through him.

Right, it might be better to do the 1-block raises on chunks, and easy enough. Depends on gameplay implications, which I've yet to test. I'm gonna at least fix blocks connected only along a diagonal (& orphaned gaps, possible orphaned 1-block high towers, etc). Not gonna do the other thing you suggest though, because I want lots of arbitrariness. It's not meant to convince as a city, just give the impression of a city.

Will ensure the decorations are narrower than the player, but I think it'll still look a little goofy. Thanks for the tips!

Wow - those textures really made a difference. I like the clean cartoony look of the textures combined with the wide-angle-lens-y effect of the camera.
Good job!

Thanks man! Hopefully it gets even better as more textures & adornments go in.

This is looking interesting, but the taller buildings obscure any paths (and potentially enemies) behind them.  It'd make a really nifty god game perspective though, I could picture a game about ruling over a tiny city-covered asteroid!

You're right about enemies being obscured (despite their search beams). I plan to fix that. Buildings obscuring paths is fundamental, rendering this statement of mine:

The idea is to give the player a good view of (almost) the entire world at a glance

shaky, as it dates from when the stereographic shader was incorrect.

What the perspective achieves now above ordinary planar projection stuff (used in other 3D stealth games) is the ability to see all around at once in an aesthetically pleasing way & with simple controls. Hell, I'll take that.

Besides, not being able to see every part of every building for picking paths hasn't been a gameplay issue yet.

[McMutton]

This is nifty. The enemies seem like creepy robots that would sound like Reapers:

[Danmark]

^ Thanks! The enemies are indeed meant to be creepy robots. No idea what they'll sound like yet, but I'm thinking something oddly menacing like

.


City with aforementioned fixing done & a bit more texture work (clicky):

[Ashkin]

That already looks a lot better

[Danmark]

Somewhat more varied texturing. Good thing Ashkin cyberbullied me into improving this aspect of Sneaky:

Still need things to break up big roofs. Skylights, hatches.

Probably-not-novel algo described below, creative types skip to the last header. Shooting for a TIGSource record girthy post here.



Connected component labeling


To add coherent variation in texturing, which is just wall color for now, I needed a way to detect different parts of buildings. Connected component labeling was the most straightforward way to go about it.

CCL splits an image into its unconnected regions, such as groups of buildings that are islands in the middle of a bunch of roads. It's a deceptively tricky thing to do in algorithms. For us humans, our capability to extract disjoint regions from an image is burned right into our visual cortex. We look at a map of the Pacific and pick out all its islands at a glance. For computers, it's a tougher problem of "folding in" numerous remote data points.

A myriad of plausible ways exist to implement CCL, and it took a while to think of something that I personally don't find obtuse. Most stuff on CCL I read was either too abstract or too pedantic, describing algorithms awkward to my mind anyway. Plus, my use case is only find blobs, do something unique to each blob's tiles. I don't need a 2D blob ID map. So I (no doubt re-)invented this data-orientedy divide-and-conquer merging algorithm:



The Algorithm


A row is defined as an origin tile and a length. Rows run left-to-right by length tiles from origin. Rows also know a parent row, initialized to the row itself, in which case it's a root row. If parent is a different row, it's a leaf or branch row (this distinction isn't crucial). If a row's parent never changed by the end of the algo, it's the parent of a region of rows. Here's how it works:

Have an array mapping row indices (henceforth IDs) to rows. Have a 2D array mapping tiles to row IDs. Logically, there is no rows[0] and a value of 0 in the tile-to-rowID map means boundary tile. So row indices range from 1 to the number of rows.

Sweep through the image bottom to top and left to right, detecting runs of object tiles bookended by boundary tiles, populating the rows array with this data. As you go, assign the ID of the row presently being laid out to the respective tiles in the tile-to-rowID map.

Next, successively merge rows of rows in this fashion (made in the premiere diagramming suite, MS Paint):




This is performed using the trees implicit in in rows' parents. Have a function that, given any row ID, gets that the root of the tree that row's in by backtracing parent relationships. Perform this for both neighbor tiles along the rows-of-rows boundaries. Take the root whose ID is lower & assign it as the parent to the root whose ID is higher (you can eliminate cases where they're equal a-priori in the sweep).

After the final merge across the middle of the image, you're done. You can use the row-to-root function to get the region (ID of root row) the row is in. But at this point I make another array mapping row ID to region ID.



Observations


Tons of room for optimization I won't do because it's already way more than fast enough for Sneaky, but it's fun to think about.

While tiles may be accessed several times, each tile boundary is considered exactly once, unlike in naive CCL algorithms. You could do a tiles-to-boundaries pass so as to access each tile once as well, which may make sense as you could obtain the row pairs needed for the merging stage ahead of time, rather than doing it while merging. You only need top/bottom tile boundaries, as sides are fully accounted for when rows are created.

Easy to see that the max number of steps to find one's parent is bounded logarithmically against the height of the image. Average depends on image structure. Anyway, it's the only term not constant against the number of tiles. Although I flatten the trees in a single pass at the end, if you flatten-as-you-merge, the algorithm runs in time linear to the number of tiles, because the max steps becomes 2.

My 64^2 cities have a mere 400-500 building rows. In the pathological checkerboard pattern case, it'd be 2048 rows (64^2/2). By using rows instead of tiles as primitives, you get plenty of cheap mileage, but moreso for well-structured data. To scale the algorithm to bigger images, it's probably best to have a separate array mapping row IDs to to parents, because for the merging stage, only this data & the tile-to-row map (or precomputed boundaries) are needed.

It's somewhat parallelizable. With minimal modification, there are image height number of independent work units in row creation, and image height/2 units in the first merge step. Merges are independent, but the number done per step halves every step all the way to 1, so the algo serializes. Better approach is to split the image into big tiles of pixels, perform the algo on each, then merge them in a parallel fashion.



Usage in procedural generation


I do 5 passes of CCL, one for each nonzero/building height level. All tiles of each blob at each height level are assigned the same random color. Any walls below the ground/roof of that tile are given the tile's color. That's it.

Sometimes it leads to patterns that make the world seem 3D-er than it really is, a nice side-effect.



Pseudo-intellectual screed


CCL a cool tool wud recommend

It gets me thinking about top-down "big features are added finer features" and bottom-up "fine features coalesce into big features" approaches to procedural generation. I think programmers are tempted to emphasize the former because it feeds their God complexes it's easier to control & more intuitive.

For instance, in a roguelike, generating rooms & connecting them with corridors. That's top-down. Introversion's city generation from before they switched to a lame tycoon game is largely top-down. Noise techniques are one or the other. Voronoi diagrams and such are bottom-up. Really, any algorithm is gonna range somewhere between the two.

Point is, top-down and bottom-up are valid and produce unique results. I've probably overemphasized bottom-up with things like the CCL texturing scheme & building & road generation (essentially the whole thing). Yet I'm pleased with the results, always coming across curious yet-unseen structures, without even fiddling with the generation parameters. I often think "wow, I'd never think to design that thing". Good, because originally I was gonna prefab some buildings & distribute instances, then put roads around them...

If you combined lots of bottom-up and top-down techniques in good balance, you'd have something really special. Sneaky is not that thing.
Oh well!

[Danmark]

Not gonna win any awards for UI design but it gets the job done:

The parameters I've been using thus far are forever enshrined as the defaults, so there's always something decent to start from. Embarrassingly, I forgot to add an entire (& rather crucial) parameter to the GUI, so the variety shown below isn't what it should be. Odd changes in sliders thanks to crashes & too infrequent saving. Goofs all around. Anyway, all is clicky:

Next up, figure out which objects to place throughout cities. Been thinking of making power lines that are very visible means for enemies to teleport short distances, so they can better encircle the player.

Oh, and I see Photobucket downscaled a couple images above. Does anyone know a better free image host?

[Aedion]

Imgur is always nice.