{"id":42400,"date":"2018-04-10T06:00:03","date_gmt":"2018-04-10T10:00:03","guid":{"rendered":"http:\/\/shamusyoung.com\/twentysidedtale\/?p=42400"},"modified":"2018-04-10T12:15:14","modified_gmt":"2018-04-10T16:15:14","slug":"pixel-city-redux-1-more-pixels","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=42400","title":{"rendered":"Pixel City Redux #1: More Pixels"},"content":{"rendered":"<p>The programming bug has bitten again. This is bad. I&#8217;ve got other writing I need to do. My Wolfenstein series ends in two days. If I don&#8217;t get the next series done then you folks won&#8217;t have anything to read on Thursdays. Still, this project got stuck in my head and after a week or so of not working on it I realized I wasn&#8217;t getting anything else done because I was spending all my mental energy just trying to not think about this. Now I&#8217;m hoping that if I put a few days into this I&#8217;ll be able to think about other things.<\/p>\n<p>A lot of things brought this about. <a href=\"?p=42097\">My time with Grand Theft Auto V<\/a> has got me thinking about  the problem of crafting urban gamespace and the terrifying expense and complexity of the problem. My friend Paul got me thinking about programming again. Out of the blue, a couple of people sent emails mentioning or asking about <a href=\"?p=2940\">Pixel City<\/a>, a project I did way back in 2009. Also, <a href=\"?p=42328\">I&#8217;ve recently played Left 4 Dead again<\/a>, and that game was one of the inspirations behind Pixel City.<\/p>\n<p>If you never saw Pixel City, it was a programming project where I tried to fake a city using nothing but black cubes and lit windows. It turned out okay:<\/p>\n<p><table class='nomargin' cellspacing='0' width='100%' cellpadding='0' align='center' border='0'><tr><td><iframe loading=\"lazy\" width=\"1024\" height=\"576\" src=\"https:\/\/www.youtube.com\/embed\/-d2-PtK4F6Y\" frameborder=\"0\" allowfullscreen class=\"embed\"><\/iframe><br\/><small><a href='http:\/\/www.youtube.com\/watch?v=-d2-PtK4F6Y'>Link (YouTube)<\/a><\/small><\/td><\/tr><\/table><\/p>\n<p>I want to do a next-generation version of this that can be explored on foot. (Or at least, from ground level. I doubt I&#8217;ll make actual walking mechanics<span class='snote' title='1'>Spoiler: Wrong!.<\/span>.) I&#8217;m not trying to make a game or anything<span class='snote' title='2'>This is still true.<\/span>. I just want to make a city using nothing but code. <\/p>\n<p>I also want to mess around with some rendering tricks I&#8217;ve been thinking about. I like the idea of taking a full-color scene and crushing it down to EGA or even CGA color levels. Maybe experiment with dithering? I&#8217;m just curious what that sort of effect will look like in motion.<\/p>\n<h3>Goals<\/h3>\n<p>It&#8217;s important to set goals now so that when I fail to meet them later we know which parts of the project I&#8217;m supposed to be ashamed of. Here&#8217;s what I&#8217;m shooting for:<\/p>\n<p><!--more--><\/p>\n<ol>\n<li>A city of proper &#8220;videogame&#8221; size. It doesn&#8217;t need to be Manhattan, but it needs to be big enough to FEEL like Manhattan in terms of how players perceive scale within a gameworld.\n<li>It needs to run in realtime. Decent framerate. I mean, I&#8217;m not aiming for &#8220;playable&#8221; or anything, but if my world is slow to the point of being annoying or uncomfortable to navigate then that&#8217;s not good enough.\n<li>The procgen stuff needs to run in a reasonable time. Say 15 seconds or less. I want to hit a button and get a city without needing to wait for half an hour to see the result.\n<li>The buildings in Pixel City were pretty good, but I&#8217;d like to revisit those ideas and maybe make some more interesting shapes.\n<li>The world needs to have the framework for detail, even if I ultimately don&#8217;t put that detail in the city. Like, I&#8217;m not planning on learning Blender so I can make streetlights, trash cans, traffic lights, newsstands, vending machines, pay phones, parking meters, dumpsters, fire hydrants, benches, road signs, bus shelters, billboards, road signs, and bike racks. This is a programming project, not an art one. But maybe I&#8217;ll put some simple primitives in the world to show that I know where these kinds of objects WOULD go. We&#8217;ll see.\n<\/ol>\n<p>To keep things from getting too crazy and having the whole project spiral out of control, I want to constrain it to something I can do in a few days or a week. So let&#8217;s put some limits on the scope of the project:<\/p>\n<ol>\n<li>The ground will be flat. I&#8217;m not going to mess around with fitting a city to rolling terrain. That can complicate things tenfold.\n<li>No cars, pedestrians, or other things that will require tons of programming \/ art.\n<li>No building interiors.\n<li>The city will be night only. I&#8217;m not going to make the buildings featureless black cubes like in the original Pixel City, but nighttime lighting conditions can cover a lot of corner-cutting.\n<li>I&#8217;m not going to use procgen textures this time. That was fun last time around, but this time if I need a texture map I&#8217;ll spend five minutes bashing pixels together in an image editor rather than spend two hours trying to write code to accomplish the same thing.\n<\/ol>\n<p>I&#8217;m starting this project in C++, using my usual framework<span class='snote' title='3'>Spoiler: It won&#8217;t stay there.<\/span> of SDL and OpenGL. <\/p>\n<p>Note that the timeline is going to be a bit wonky. By convention I write these entries in present tense, but I&#8217;m actually writing this after several days of development<span class='snote' title='4'>I wrongly suspected that I could pour a couple of days into this and go back to doing other things and I wouldn&#8217;t have anything worth writing about.<\/span>. I&#8217;m going to publish these entries once a week, but each entry represents roughly a day or so of development time. By the time we get to the fourth entry we&#8217;ll be well into May, but you&#8217;ll still be reading about what I was doing at the end of March. Also, while I&#8217;m writing this from the future, I&#8217;m not writing this from particularly <em>far<\/em> in the future. This entire project might hit a wall or come to nothing. I might lose interest. While I don&#8217;t know what will become of the project as I&#8217;m writing this now, I&#8217;ll probably know by the time you read this.<\/p>\n<p>I realize this is horribly confusing. Sorry. For the sake of brevity and basic comprehension I&#8217;m going to continue to write in present tense, regardless of what&#8217;s going on in a temporal sense. Otherwise this whole series will come off sounding like <a href=\"https:\/\/en.wikipedia.org\/wiki\/Primer_(film)\">Primer<\/a> fanfiction.<\/p>\n<p>Anyway. Enough disclaimers. Let&#8217;s get started.<\/p>\n<h3>Roads<\/h3>\n<p>So the most basic problem is &#8220;How do you form the city layout?&#8221; This is one of those annoying problems that&#8217;s obvious to do by hand but rather fiddly to do with code. A child can draw you a passable street layout, but then again a child can identify pictures of birds and it turns out that&#8217;s also <a href=\"https:\/\/xkcd.com\/1425\/\">a really hard problem<\/a> for computers to solve. <\/p>\n<p>Sure, you can do the brute-force thing of having streets form a strict grid. Every street can be locked to a world axis. But that&#8217;s boring. I want something that can gracefully handle T-junctions, diagonals, and so on. <\/p>\n<p>So here&#8217;s what I come up with:<\/p>\n<p><div class='imagefull'><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/pixelcity2_start1.jpg' width=100% alt='There. Done. Whaddya think?' title='There. Done. Whaddya think?'\/><\/div><div class='mouseover-alt'>There. Done. Whaddya think?<\/div><\/p>\n<p>The program will draw lines to form a mangled grid. No curves to start with, but the roads will meet at odd angles and such. These lines are streets. <\/p>\n<p>Then each street will put down marker points for where a sidewalk will go. These points will have a direction associated with them and will be oriented with &#8220;right side forward&#8221; scheme. Imagine you&#8217;re driving down the road on right side. To your right will be (invisible to the player) markers that point forward, just off the side of the road. On the other side of the street will be the same kind of markers pointing in the opposite direction.<\/p>\n<p><div class='imagefull'><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/pixelcity2_start2.jpg' width=100% alt='You can&apos;t tell, but all those red dots are actually arrows.' title='You can&apos;t tell, but all those red dots are actually arrows.'\/><\/div><div class='mouseover-alt'>You can&apos;t tell, but all those red dots are actually arrows.<\/div><\/p>\n<p>Once that&#8217;s done, we&#8217;ll have all these crazy criss-crossing groups of points. It will be chaos. If we use these points to create sidewalks then we&#8217;d end up with sidewalks all over the roads. So the second step is to have each road &#8220;clean up&#8221; any sidewalk points that are encroaching on its space. Once that&#8217;s done, we should have something that looks like this:<\/p>\n<p><div class='imagefull'><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/pixelcity2_start3.jpg' width=100% alt='Well, they&apos;re not so much ARROWS as tiny little lines that are red on one end but green on the other. Good enough, since they&apos;re just to help me visualize.' title='Well, they&apos;re not so much ARROWS as tiny little lines that are red on one end but green on the other. Good enough, since they&apos;re just to help me visualize.'\/><\/div><div class='mouseover-alt'>Well, they&apos;re not so much ARROWS as tiny little lines that are red on one end but green on the other. Good enough, since they&apos;re just to help me visualize.<\/div><\/p>\n<p>You can see we already have city blocks isolated as little islands. Now I can just grab a point and go the way its arrow indicates, grabbing the next closest point in that direction. If I&#8217;m confused about which point to choose, I can favor right turns, which ought to let me enclose all of these city blocks. The only exception is those bits around the edge. If the program hits a dead end, it assumes it&#8217;s on the edge of the city and just throws away all the points. <\/p>\n<p><div class='imagefull'><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/pixelcity2_start4.jpg' width=100% alt='The white outlines are city blocks that it was able to complete. Red ones are blocks that didn&apos;t work out.' title='The white outlines are city blocks that it was able to complete. Red ones are blocks that didn&apos;t work out.'\/><\/div><div class='mouseover-alt'>The white outlines are city blocks that it was able to complete. Red ones are blocks that didn&apos;t work out.<\/div><\/p>\n<p>This works. I can then use these points as an outline to create the polygons. <\/p>\n<p>(If this seems like an odd way to go about this, you&#8217;re right. I&#8217;ll come back to this in a few days. I&#8217;ll talk more about this then.)<\/p>\n<p>So now I have these enclosed shapes, which form city blocks. Now I just need to put buildings on them.<\/p>\n<p>I already have these points scattered everywhere. They&#8217;re a perfect starting point for this job. Here&#8217;s what you do:<\/p>\n<p>Grab a city block. Within that block, grab the first point that makes up its perimeter. This point also has a vector, indicating which way to go to walk down the sidewalk. (Walking on the right side of the street.) All I need to do is make a right-angle turn from where this thing is pointing, and I should be facing the big empty interior of the block. From there I can attempt to slap down a rectangle, aligned with this sidewalk. Let&#8217;s start with one that&#8217;s 10 meters x 10 meters. This rectangle will be the site for a building.<\/p>\n<p>If the rectangle doesn&#8217;t overlap with the sidewalk, and it doesn&#8217;t overlap with any other building sites, then it&#8217;s good. I can nudge it a little larger and see if it still fits. I try making it wider. Then deeper<span class='snote' title='5'>That is, the back of the building is father away from the sidewalk.<\/span>. Then wider again. I try to make it as large as I can get away with, while also keeping it roughly square. I go around the block, fitting in rectangular sites like this to fill in each block as much as possible.<\/p>\n<p><div class='imagefull'><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/pixelcity2_start5.jpg' width=100% alt='Now we&apos;re getting somewhere.' title='Now we&apos;re getting somewhere.'\/><\/div><div class='mouseover-alt'>Now we&apos;re getting somewhere.<\/div><\/p>\n<p>Once complete, I have lines for streets, rough outlines for city blocks, and scattered rectangles for building sites. Technically this is everything we need to build a big city like in the original Pixel City. (For the record, those red incomplete blocks on the edge of the city aren&#8217;t really relevant anymore. The program throws them away, but they&#8217;re still being drawn here for development purposes.)<\/p>\n<p>Just to get a sense of how this is looking in terms of scale, I turn it into polygons so I can have a look around:<\/p>\n<p><div class='imagefull'><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/pixelcity2_start6.jpg' width=100% alt='Eat your heart out, Crytek.' title='Eat your heart out, Crytek.'\/><\/div><div class='mouseover-alt'>Eat your heart out, Crytek.<\/div><\/p>\n<p>I realize this doesn&#8217;t look very impressive in terms of videogame graphics, but I&#8217;m pretty happy with what I&#8217;m seeing. Try not to think of these cuboids as literal buildings but instead as a representation of the volume for where a building would go. Also, you sort of have to imagine a street and sidewalk textures and such.<\/p>\n<p>The point is that I like how this is working out spatially. Since I&#8217;m being a little more ambitious this time, it&#8217;s going to take us a bit longer to reach the point where we see something interesting. This is particularly true because I&#8217;m about to do something really absurd and silly. I&#8217;m about to start over with different tools.<\/p>\n<p><div class='imagefull'><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/pixelcity2_start7.jpg' width=100% alt='Great, now we just need to add EVERYTHING ELSE and we&apos;re done.' title='Great, now we just need to add EVERYTHING ELSE and we&apos;re done.'\/><\/div><div class='mouseover-alt'>Great, now we just need to add EVERYTHING ELSE and we&apos;re done.<\/div><\/p>\n<p>Next week we&#8217;re doing this again, except in Unity.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The programming bug has bitten again. This is bad. I&#8217;ve got other writing I need to do. My Wolfenstein series ends in two days. If I don&#8217;t get the next series done then you folks won&#8217;t have anything to read on Thursdays. Still, this project got stuck in my head and after a week or [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-42400","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/42400","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=42400"}],"version-history":[{"count":17,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/42400\/revisions"}],"predecessor-version":[{"id":42420,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/42400\/revisions\/42420"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=42400"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=42400"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=42400"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}