Created
February 15, 2015 19:32
-
-
Save anonymous/7dbe17dfe726999856f4 to your computer and use it in GitHub Desktop.
Core algorithm for procedural city generation article (http://www.tmwhere.com)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # author: tmwhere.com | |
| # --- third party dependencies | |
| PIXI = require('pixi.dev') | |
| _ = require('lodash') | |
| noise = require('perlin').noise | |
| Quadtree = require('quadtree').Quadtree | |
| seedrandom = require('seedrandom') | |
| # --- | |
| math = require('modules/math') | |
| util = require('modules/utility') | |
| collision = require('modules/collision') | |
| config = require('game_modules/config') | |
| class Segment extends collision.CollisionObject | |
| @End: | |
| START: "start" | |
| END: "end" | |
| constructor: (start, end, t, q) -> | |
| obj = @ | |
| start = _.cloneDeep(start) | |
| end = _.cloneDeep(end) | |
| t = util.defaultFor(t, 0) | |
| q = util.defaultFor(q, {}, true) | |
| @width = if q.highway then config.mapGeneration.HIGHWAY_SEGMENT_WIDTH else config.mapGeneration.DEFAULT_SEGMENT_WIDTH | |
| @collider = new collision.CollisionObject(this, collision.CollisionObject.Type.LINE, {start: start, end: end, width: @width}) | |
| @roadRevision = 0 | |
| @dirRevision = undefined | |
| @lengthRevision = undefined | |
| @cachedDir = undefined | |
| @cachedLength = undefined | |
| # representation of road | |
| @r = | |
| start: start | |
| end: end | |
| setStart: (val) -> | |
| @start = val | |
| obj.collider.updateCollisionProperties({start: @start}) | |
| obj.roadRevision++ | |
| setEnd: (val) -> | |
| @end = val | |
| obj.collider.updateCollisionProperties({end: @end}) | |
| obj.roadRevision++ | |
| # time-step delay before this road is evaluated | |
| @t = t | |
| # meta-information relevant to global goals | |
| @q = q | |
| # links backwards and forwards | |
| @links = | |
| b: [] | |
| f: [] | |
| @users = [] | |
| [@maxSpeed, @capacity] = | |
| if (q.highway) | |
| [1200, 12] | |
| else | |
| [800, 6] | |
| currentSpeed: -> | |
| # subtract 1 from user's length so that a single user can go full speed | |
| Math.min(config.gameLogic.MIN_SPEED_PROPORTION, 1 - Math.max(0, @users.length - 1) / @capacity) * @maxSpeed | |
| # clockwise direction | |
| dir: -> | |
| if (@dirRevision != @roadRevision) | |
| @dirRevision = @roadRevision | |
| vector = math.subtractPoints(@r.end, @r.start) | |
| @cachedDir = -1 * math.sign(math.crossProduct({x:0, y: 1}, vector)) * math.angleBetween({x: 0, y: 1}, vector) | |
| return @cachedDir | |
| length: -> | |
| if (@lengthRevision != @roadRevision) | |
| @lengthRevision = @roadRevision | |
| @cachedLength = math.length(@r.start, @r.end) | |
| return @cachedLength | |
| debugLinks: -> | |
| @q.color = 0x00FF00 | |
| _.each(@links.b, (backwards) -> | |
| backwards.q.color = 0xFF0000 | |
| ) | |
| _.each(@links.f, (forwards) -> | |
| forwards.q.color = 0x0000FF | |
| ) | |
| startIsBackwards: -> | |
| if (@links.b.length > 0) | |
| math.equalV(@links.b[0].r.start, @r.start) || | |
| math.equalV(@links.b[0].r.end, @r.start) | |
| else | |
| math.equalV(@links.f[0].r.start, @r.end) || | |
| math.equalV(@links.f[0].r.end, @r.end) | |
| cost: -> | |
| @length() / @currentSpeed() | |
| costTo: (other, fromFraction) -> | |
| segmentEnd = @endContaining(other) | |
| return @cost() * | |
| if fromFraction? | |
| switch segmentEnd | |
| when Segment.End.START then fromFraction | |
| when Segment.End.END then (1-fromFraction) | |
| else | |
| 0.5 | |
| neighbours: -> | |
| @links.f.concat(@links.b) | |
| endContaining: (segment) -> | |
| startBackwards = @startIsBackwards() | |
| if @links.b.indexOf(segment) != -1 | |
| return if startBackwards then Segment.End.START else Segment.End.END | |
| else if @links.f.indexOf(segment) != -1 | |
| return if startBackwards then Segment.End.END else Segment.End.START | |
| else | |
| undefined | |
| linksForEndContaining: (segment) -> | |
| if @links.b.indexOf(segment) != -1 | |
| @links.b | |
| else if @links.f.indexOf(segment) != -1 | |
| @links.f | |
| else | |
| undefined | |
| split: (point, segment, segmentList, qTree) -> | |
| startIsBackwards = @startIsBackwards() | |
| splitPart = segmentFactory.fromExisting(this) | |
| addSegment(splitPart, segmentList, qTree) | |
| splitPart.r.setEnd(point) | |
| @r.setStart(point) | |
| # links are not copied using the preceding factory method. | |
| # copy link array for the split part, keeping references the same | |
| splitPart.links.b = @links.b.slice(0) | |
| splitPart.links.f = @links.f.slice(0) | |
| # determine which links correspond to which end of the split segment | |
| if (startIsBackwards) | |
| firstSplit = splitPart | |
| secondSplit = this | |
| fixLinks = splitPart.links.b | |
| else | |
| firstSplit = this | |
| secondSplit = splitPart | |
| fixLinks = splitPart.links.f | |
| _.each(fixLinks, (link) -> | |
| index = link.links.b.indexOf(this) | |
| if (index != -1) | |
| link.links.b[index] = splitPart | |
| else | |
| index = link.links.f.indexOf(this) | |
| link.links.f[index] = splitPart | |
| , this) | |
| firstSplit.links.f = [] | |
| firstSplit.links.f.push(segment) | |
| firstSplit.links.f.push(secondSplit) | |
| secondSplit.links.b = [] | |
| secondSplit.links.b.push(segment) | |
| secondSplit.links.b.push(firstSplit) | |
| segment.links.f.push(firstSplit) | |
| segment.links.f.push(secondSplit) | |
| segmentFactory = do -> | |
| return { | |
| fromExisting: (segment, t, r, q) -> | |
| t = util.defaultFor(t, segment.t) | |
| r = util.defaultFor(r, segment.r) | |
| q = util.defaultFor(q, segment.q) | |
| return new Segment(r.start, r.end, t, q) | |
| , | |
| usingDirection: (start, dir, length, t, q) -> | |
| # default to east | |
| dir = util.defaultFor(dir, 90) | |
| length = util.defaultFor(length, config.mapGeneration.DEFAULT_SEGMENT_LENGTH) | |
| end = | |
| x: start.x + length*math.sinDegrees(dir), | |
| y: start.y + length*math.cosDegrees(dir) | |
| return new Segment(start, end, t, q) | |
| } | |
| heatmap = do -> | |
| { | |
| popOnRoad: (r) -> | |
| (@populationAt(r.start.x, r.start.y) + @populationAt(r.end.x, r.end.y))/2 | |
| populationAt: (x, y) -> | |
| value1 = (noise.simplex2(x/10000, y/10000) + 1) / 2 | |
| value2 = (noise.simplex2(x/20000 + 500, y/20000 + 500) + 1) / 2 | |
| value3 = (noise.simplex2(x/20000 + 1000, y/20000 + 1000) + 1) / 2 | |
| Math.pow((value1 * value2 + value3) / 2, 2) | |
| } | |
| doRoadSegmentsIntersect = (r1, r2) -> | |
| math.doLineSegmentsIntersect(r1.start, r1.end, r2.start, r2.end, true) | |
| localConstraints = (segment, segments, qTree, debugData) -> | |
| action = | |
| priority: 0, | |
| func: undefined, | |
| q: {} | |
| matches = qTree.retrieve(segment.collider.limits()) | |
| for i in [0..matches.length-1] by 1 | |
| other = matches[i].o | |
| # intersection check | |
| if (action.priority <= 4) | |
| intersection = doRoadSegmentsIntersect(segment.r, other.r) | |
| if (intersection) | |
| if (!action.q.t? || intersection.t < action.q.t) | |
| action.q.t = intersection.t | |
| do (other, intersection) -> | |
| action.priority = 4 | |
| action.func = -> | |
| # if intersecting lines are too similar don't continue | |
| if util.minDegreeDifference(other.dir(), segment.dir()) < config.mapGeneration.MINIMUM_INTERSECTION_DEVIATION | |
| return false | |
| other.split(intersection, segment, segments, qTree) | |
| segment.r.end = intersection | |
| segment.q.severed = true | |
| if (debugData?) | |
| if (!debugData.intersections?) | |
| debugData.intersections = [] | |
| debugData.intersections.push( | |
| x: intersection.x | |
| y: intersection.y | |
| ) | |
| return true | |
| # snap to crossing within radius check | |
| if (action.priority <= 3) | |
| # current segment's start must have been checked to have been created. | |
| # other segment's start must have a corresponding end. | |
| if (math.length(segment.r.end, other.r.end) <= config.mapGeneration.ROAD_SNAP_DISTANCE) | |
| do (other) -> | |
| point = other.r.end | |
| action.priority = 3 | |
| action.func = -> | |
| segment.r.end = point | |
| segment.q.severed = true | |
| # update links of otherSegment corresponding to other.r.end | |
| links = if other.startIsBackwards() then other.links.f else other.links.b | |
| # check for duplicate lines, don't add if it exists | |
| # this should be done before links are setup, to avoid having to undo that step | |
| if _.any(links, (link) -> | |
| ((math.equalV(link.r.start, segment.r.end) && math.equalV(link.r.end, segment.r.start)) || | |
| (math.equalV(link.r.start, segment.r.start) && math.equalV(link.r.end, segment.r.end)))) | |
| return false | |
| _.each(links, (link) -> | |
| # pick links of remaining segments at junction corresponding to other.r.end | |
| link.linksForEndContaining(other).push(segment) | |
| # add junction segments to snapped segment | |
| segment.links.f.push(link) | |
| ) | |
| links.push(segment) | |
| segment.links.f.push(other) | |
| if (debugData?) | |
| if (!debugData.snaps?) | |
| debugData.snaps = [] | |
| debugData.snaps.push( | |
| x: point.x | |
| y: point.y | |
| ) | |
| return true | |
| # intersection within radius check | |
| if (action.priority <= 2) | |
| {distance2, pointOnLine, lineProj2, length2} = math.distanceToLine(segment.r.end, other.r.start, other.r.end) | |
| if (distance2 < config.mapGeneration.ROAD_SNAP_DISTANCE * config.mapGeneration.ROAD_SNAP_DISTANCE && | |
| lineProj2 >= 0 && lineProj2 <= length2) | |
| do (other) -> | |
| point = pointOnLine | |
| action.priority = 2 | |
| action.func = -> | |
| segment.r.end = point | |
| segment.q.severed = true | |
| # if intersecting lines are too closely aligned don't continue | |
| if util.minDegreeDifference(other.dir(), segment.dir()) < config.mapGeneration.MINIMUM_INTERSECTION_DEVIATION | |
| return false | |
| other.split(point, segment, segments, qTree) | |
| if (debugData?) | |
| if (!debugData.intersectionsRadius?) | |
| debugData.intersectionsRadius = [] | |
| debugData.intersectionsRadius.push( | |
| x: point.x | |
| y: point.y | |
| ) | |
| return true | |
| if (action.func) | |
| return action.func() | |
| return true | |
| globalGoals = do -> | |
| return { | |
| generate: (previousSegment) -> | |
| newBranches = [] | |
| if (!previousSegment.q.severed) | |
| template = (direction, length, t, q) -> | |
| segmentFactory.usingDirection(previousSegment.r.end, direction, length, t, q) | |
| # used for highways or going straight on a normal branch | |
| templateContinue = _.partialRight(template, previousSegment.length(), 0, previousSegment.q) | |
| # not using q, i.e. not highways | |
| templateBranch = _.partialRight( | |
| template, config.mapGeneration.DEFAULT_SEGMENT_LENGTH, if previousSegment.q.highway then config.mapGeneration.NORMAL_BRANCH_TIME_DELAY_FROM_HIGHWAY else 0) | |
| continueStraight = templateContinue(previousSegment.dir()) | |
| straightPop = heatmap.popOnRoad(continueStraight.r) | |
| if (previousSegment.q.highway) | |
| randomStraight = templateContinue(previousSegment.dir() + config.mapGeneration.RANDOM_STRAIGHT_ANGLE()) | |
| randomPop = heatmap.popOnRoad(randomStraight.r) | |
| roadPop | |
| if (randomPop > straightPop) | |
| newBranches.push(randomStraight) | |
| roadPop = randomPop | |
| else | |
| newBranches.push(continueStraight) | |
| roadPop = straightPop | |
| if (roadPop > config.mapGeneration.HIGHWAY_BRANCH_POPULATION_THRESHOLD) | |
| if (Math.random() < config.mapGeneration.HIGHWAY_BRANCH_PROBABILITY) | |
| leftHighwayBranch = templateContinue(previousSegment.dir() - 90 + config.mapGeneration.RANDOM_BRANCH_ANGLE()) | |
| newBranches.push(leftHighwayBranch) | |
| else if (Math.random() < config.mapGeneration.HIGHWAY_BRANCH_PROBABILITY) | |
| rightHighwayBranch = templateContinue(previousSegment.dir() + 90 + config.mapGeneration.RANDOM_BRANCH_ANGLE()) | |
| newBranches.push(rightHighwayBranch) | |
| else if (straightPop > config.mapGeneration.NORMAL_BRANCH_POPULATION_THRESHOLD) | |
| newBranches.push(continueStraight) | |
| if (straightPop > config.mapGeneration.NORMAL_BRANCH_POPULATION_THRESHOLD) | |
| if (Math.random() < config.mapGeneration.DEFAULT_BRANCH_PROBABILITY) | |
| leftBranch = templateBranch(previousSegment.dir() - 90 + config.mapGeneration.RANDOM_BRANCH_ANGLE()) | |
| newBranches.push(leftBranch) | |
| else if (Math.random() < config.mapGeneration.DEFAULT_BRANCH_PROBABILITY) | |
| rightBranch = templateBranch(previousSegment.dir() + 90 + config.mapGeneration.RANDOM_BRANCH_ANGLE()) | |
| newBranches.push(rightBranch) | |
| for i in [0..newBranches.length-1] by 1 | |
| do (branch = newBranches[i]) -> | |
| branch.setupBranchLinks = -> | |
| # setup links between each current branch and each existing branch stemming from the previous segment | |
| _.each(previousSegment.links.f, (link) -> | |
| @links.b.push(link) | |
| link.linksForEndContaining(previousSegment).push(this) | |
| , @) | |
| previousSegment.links.f.push(@) | |
| @links.b.push(previousSegment) | |
| return newBranches | |
| } | |
| addSegment = (segment, segmentList, qTree) -> | |
| segmentList.push(segment) | |
| qTree.insert(segment.collider.limits()) | |
| generate = (seed) -> | |
| debugData = {} | |
| Math.seedrandom(seed) | |
| # NB: this perlin noise library only supports 65536 different seeds | |
| noise.seed(Math.random()) | |
| priorityQ = [] | |
| # setup first segments in queue | |
| do -> | |
| rootSegment = new Segment({x: 0, y: 0}, {x: config.mapGeneration.HIGHWAY_SEGMENT_LENGTH, y: 0}, 0, {highway: true}) | |
| oppositeDirection = segmentFactory.fromExisting(rootSegment) | |
| newEnd = | |
| x: rootSegment.r.start.x - config.mapGeneration.HIGHWAY_SEGMENT_LENGTH | |
| y: oppositeDirection.r.end.y | |
| oppositeDirection.r.setEnd(newEnd) | |
| oppositeDirection.links.b.push(rootSegment) | |
| rootSegment.links.b.push(oppositeDirection) | |
| priorityQ.push(rootSegment) | |
| priorityQ.push(oppositeDirection) | |
| segments = [] | |
| qTree = new Quadtree(config.mapGeneration.QUADTREE_PARAMS, | |
| config.mapGeneration.QUADTREE_MAX_OBJECTS, config.mapGeneration.QUADTREE_MAX_LEVELS) | |
| while (priorityQ.length > 0 && segments.length < config.mapGeneration.SEGMENT_COUNT_LIMIT) | |
| # pop smallest r(ti, ri, qi) from Q (i.e., smallest 't') | |
| minT = undefined | |
| minT_i = 0 | |
| _.each(priorityQ, (segment, i) -> | |
| if (!minT? || segment.t < minT) | |
| minT = segment.t | |
| minT_i = i | |
| ) | |
| minSegment = priorityQ.splice(minT_i, 1)[0] | |
| accepted = localConstraints(minSegment, segments, qTree, debugData) | |
| if (accepted) | |
| if (minSegment.setupBranchLinks?) | |
| minSegment.setupBranchLinks() | |
| addSegment(minSegment, segments, qTree) | |
| _.each(globalGoals.generate(minSegment), (newSegment) -> | |
| newSegment.t = minSegment.t + 1 + newSegment.t | |
| priorityQ.push(newSegment) | |
| ) | |
| id = 0 | |
| for segment in segments | |
| segment.id = id++ | |
| console.log("#{segments.length} segments generated.") | |
| return { | |
| segments: segments | |
| qTree: qTree | |
| heatmap: heatmap | |
| debugData: debugData | |
| } | |
| module.exports = { | |
| Segment: Segment | |
| generate: generate | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The full source for the project can be found here: https://github.com/t-mw/citygen