gencitymap

package
v0.0.0-...-8d0fdad Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 16, 2024 License: Apache-2.0 Imports: 17 Imported by: 0

README

gencitymap

This is a small tool to generate a city map based on simple rules wrt road branching and such. Right now, it is just a proof of concept, but in the future it'll offer custom configurations, different map styles, and so on.

alt text

Tensor Fields

This is based on the work of these folks: https://github.com/ProbableTrain/MapGenerator

NOTE: HEAVILY WIP!! Do not use this yet!

TODO
  • Add coastline, water, rivers, etc.
  • Add graph generation from streamlines
  • Add polygon extraction for identifying plots and buildings
  • Make code less buggy (crashes constantly)
  • Add more map styles
  • Eliminate artifacts in polygon extraction
  • Investigate polygon extraction failure in polygons that contain dangling roads

alt text

Documentation

Overview

Package gencitymap generates a city map.

Index

Constants

View Source 
const (
	FTRadialField = iota // RadialField represents a radial field.
	FTGridField          // GridField represents a grid field.
)

Variables

View Source 
var (
	HighwayConfig = SegmentTypeConfig{
		LengthMin:         200,
		LengthVariation:   0.1,
		AngleMin:          10.0,
		AngleVariance:     1.0,
		AngleReversal:     true,
		BranchingChance:   0.3,
		BranchingAngle:    90.0,
		BranchingReversal: true,
	}
	StreetConfig = SegmentTypeConfig{
		LengthMin:            100,
		LengthVariation:      0.5,
		AngleVariance:        4.0,
		AngleReversal:        true,
		BranchingChance:      0.7,
		BranchingAngle:       90.0,
		BranchingReversal:    true,
		BranchSameType:       true,
		BranchSameTypeChance: 0.2,
	}
	FootpathConfig = SegmentTypeConfig{
		LengthMin:       50,
		LengthVariation: 0.6,
		AngleVariance:   3.0,
		AngleReversal:   true,
		BranchingChance: 0.5,
		BranchingAngle:  90.0,
	}
)
View Source 
var DefaultMapConfig = &MapConfig{
	SeedRoots: func() []*Segment {
		root1 := &Segment{
			Point:  vectors.NewVec2(0, 0),
			Length: 100,
			Type:   0,
		}

		return []*Segment{root1}
	}, Rules: []*SegmentTypeConfig{
		&HighwayConfig,
		&StreetConfig,
		&FootpathConfig,
	},
}
View Source 
var DefaultNoiseParams = &NoiseParams{
	Seed:             0,
	globalNoise:      true,
	noiseSizePark:    2,
	noiseAnglePark:   9,
	noiseSizeGlobal:  3,
	noiseAngleGlobal: 2,
}
View Source 
var DefaultStreamlineParams = &StreamlineParams{
	Dsep:              20,
	Dtest:             15,
	Dstep:             1,
	Dcirclejoin:       5,
	Dlookahead:        40,
	Joinangle:         0.1,
	PathIterations:    2000,
	SeedTries:         30,
	SimplifyTolerance: 10,
	CollideEarly:      0.01,
}

Functions

func AveragePoint 

func AveragePoint(polygon []vectors.Vec2) vectors.Vec2

AveragePoint returns the average point of a polygon.

func CalcPolygonArea 

func CalcPolygonArea(polygon []vectors.Vec2) float64

func Hilbert 

func Hilbert(x uint, y uint) uint

Fast Hilbert curve algorithm by http://threadlocalmutex.com/ Ported from C++ https://github.com/rawrunprotected/hilbert_curves (public domain)

func ResizeGeometry 

func ResizeGeometry(geometry []vectors.Vec2, spacing float64, isPolygon bool) []vectors.Vec2

ResizeGeometry resizes a polygon to a given spacing.

func SubdividePolygon 

func SubdividePolygon(poly []vectors.Vec2, minArea float64) [][]vectors.Vec2

SubdividePolygon divides a polygon into smaller polygons until the minArea is reached.

Types

type BasisField 

type BasisField struct {
	Centre    vectors.Vec2
	FieldType int
	Size      float64
	Decay     float64
}

BasisField represents a basis field used for generating a city map.

func NewBasisField 

func NewBasisField(centre vectors.Vec2, size, decay float64, fieldType int) *BasisField

NewBasisField creates a new basis field.

func (*BasisField) GetCentre 

func (b *BasisField) GetCentre() vectors.Vec2

type BasisFieldInterface 

type BasisFieldInterface interface {
	GetTensor(point vectors.Vec2) *Tensor
	GetWeightedTensor(point vectors.Vec2, smooth bool) *Tensor
	GetCentre() vectors.Vec2
}

type Bush 

type Bush struct {
	// contains filtered or unexported fields
}

func (*Bush) Run 

func (b *Bush) Run() []intersection

func (*Bush) Step 

func (b *Bush) Step() bool

type BushAsyncState 

type BushAsyncState struct {
	I int
}

type BushOptions 

type BushOptions struct {
	OnFound func(p vectors.Vec2, interior []vectors.Segment) bool
}

type EulerIntegrator 

type EulerIntegrator struct {
	*FieldIntegrator
	// contains filtered or unexported fields
}

func NewEulerIntegrator 

func NewEulerIntegrator(field *TensorField, params *StreamlineParams) *EulerIntegrator

func (*EulerIntegrator) Integrate 

func (e *EulerIntegrator) Integrate(point vectors.Vec2, major bool) vectors.Vec2

type FieldIntegrator 

type FieldIntegrator struct {
	// contains filtered or unexported fields
}

func NewFieldIntegrator 

func NewFieldIntegrator(field *TensorField) *FieldIntegrator

func (*FieldIntegrator) OnLand 

func (f *FieldIntegrator) OnLand(point vectors.Vec2) bool

func (*FieldIntegrator) SampleFieldVector 

func (f *FieldIntegrator) SampleFieldVector(point vectors.Vec2, major bool) vectors.Vec2

type FieldIntegratorIf 

type FieldIntegratorIf interface {
	Integrate(point vectors.Vec2, major bool) vectors.Vec2
	OnLand(point vectors.Vec2) bool
	SampleFieldVector(point vectors.Vec2, major bool) vectors.Vec2
}

type Flatbush 

type Flatbush struct {
	NumItems    int
	NodeSize    int
	LevelBounds []int
	Boxes       []float64
	Indices     []int
	Pos         int
	MinX        float64
	MinY        float64
	MaxX        float64
	MaxY        float64
}

This code is based on https://github.com/mourner/flatbush

func NewFlatbush 

func NewFlatbush(numItems int, nodeSize int) *Flatbush

func (*Flatbush) Add 

func (f *Flatbush) Add(minX float64, minY float64, maxX float64, maxY float64)

func (*Flatbush) Finish 

func (f *Flatbush) Finish()

/ <summary> / Method to perform the indexing, to be called after adding all the boxes via <see cref="Add"/>. / </summary>

func (*Flatbush) Query 

func (f *Flatbush) Query(minX float64, minY float64, maxX float64, maxY float64, filter func(index int) bool) []int

/ <summary> / Returns a list of indices to boxes that intersect or overlap the bounding box given, <see cref="Finish"/> must be called before querying. / </summary> / <param name="minX">Min x value of the bounding box.</param> / <param name="minY">Min y value of the bounding box.</param> / <param name="maxX">Max x value of the bounding box.</param> / <param name="maxY">Max y value of the bounding box.</param> / <param name="filter">Optional filter function, if not null then only indices for which the filter function returns true will be included.</param> / <returns>List of indices that intersect or overlap with the bounding box given.</returns>

func (*Flatbush) Sort 

func (f *Flatbush) Sort(values []uint, boxes []float64, indices []int, left int, right int, nodeSize int)

custom quicksort that partially sorts bbox data alongside the hilbert values

func (*Flatbush) Swap 

func (f *Flatbush) Swap(values []uint, boxes []float64, indices []int, i int, j int)

swap two values and two corresponding boxes

func (*Flatbush) VisitQuery 

func (f *Flatbush) VisitQuery(minX float64, minY float64, maxX float64, maxY float64, visitor func(index int) bool)

/ <summary> / Invokes a function on each of the indices of boxes that intersect or overlap with the bounding box given, <see cref="Finish"/> must be called before querying. / </summary> / <param name="minX">Min x value of the bounding box.</param> / <param name="minY">Min y value of the bounding box.</param> / <param name="maxX">Max x value of the bounding box.</param> / <param name="maxY">Max y value of the bounding box.</param> / <param name="visitor">The function to visit each of the result indices, if false is returned no more results will be visited.</param>

type Graph 

type Graph struct {
	Nodes         []*Node
	Intersections []vectors.Vec2
}

func NewGraph 

func NewGraph(streamlines [][]vectors.Vec2, dstep float64, deleteDangling bool) *Graph

NewGraph creates a graph from a set of streamlines. Finds all intersections, and creates a list of Nodes.

type GridField 

type GridField struct {
	*BasisField
	Theta float64
}

func NewGridField 

func NewGridField(centre vectors.Vec2, size, decay, theta float64) *GridField

NewGridField creates a new grid field.

func (*GridField) GetTensor 

func (r *GridField) GetTensor(point vectors.Vec2) *Tensor

func (*GridField) GetWeightedTensor 

func (r *GridField) GetWeightedTensor(point vectors.Vec2, smooth bool) *Tensor

type GridStorage 

type GridStorage struct {
	// contains filtered or unexported fields
}

GridStorage is a grid-based storage for samples. NOTE: Cartesian grid accelerated data structure, Grid of cells, each containing a list of vectors.

func NewGridStorage 

func NewGridStorage(worldDimensions vectors.Vec2, origin vectors.Vec2, dsep float64) *GridStorage

NewGridStorage creates a new grid storage. NOTE: worldDimensions assumes origin of 0,0, dsep is the separation distance between samples.

func (*GridStorage) AddAll 

func (gs *GridStorage) AddAll(gridStorage *GridStorage)

AddAll adds all samples from another grid to this one.

func (*GridStorage) AddPolyline 

func (gs *GridStorage) AddPolyline(line []vectors.Vec2)

func (*GridStorage) AddSample 

func (gs *GridStorage) AddSample(v vectors.Vec2, coords *vectors.Vec2)

AddSample adds a sample to the grid. NOTE: Does not enforce separation, does not clone.

func (*GridStorage) GetNearbyPoints 

func (gs *GridStorage) GetNearbyPoints(v vectors.Vec2, distance float64) []vectors.Vec2

GetNearbyPoints returns points in cells surrounding v. Results include v, if it exists in the grid. NOTE: Returns samples (kind of) closer than distance - returns all samples in cells so approximation (square to approximate circle).

func (*GridStorage) GetSampleCoords 

func (gs *GridStorage) GetSampleCoords(worldV vectors.Vec2) vectors.Vec2

GetSampleCoords returns the cell coords corresponding to the vector. NOTE: Performance is important here - this is called at every integration step.

func (*GridStorage) IsValidSample 

func (gs *GridStorage) IsValidSample(v vectors.Vec2, dSq float64) bool

IsValidSample returns true if the sample is valid and within the world dimensions. Tests whether v is at least d away from samples. NOTE: Performance is very important - this is called at every integration step! dSq=this.dsepSq squared test distance Could be dtest if we are integrating a streamline

func (*GridStorage) VectorOutOfBounds 

func (gs *GridStorage) VectorOutOfBounds(v vectors.Vec2, bounds vectors.Vec2) bool

type Intersection 

type Intersection struct {
	// contains filtered or unexported fields
}

type Map 

type Map struct {
	// contains filtered or unexported fields
}

Map is a map.

func NewMap 

func NewMap(seed int64, cfg *MapConfig) *Map

NewMap creates a new map.

func (*Map) Dimensions 

func (m *Map) Dimensions() (float64, float64)

Dimensions returns the dimensions of the map.

func (*Map) ExportToPNG 

func (m *Map) ExportToPNG(path string) error

ExportToPNG exports the map to a PNG file.

func (*Map) Generate 

func (m *Map) Generate()

Generate generates the map.

func (*Map) GetExtent 

func (m *Map) GetExtent() (minX, minY, maxX, maxY float64)

func (*Map) Origin 

func (m *Map) Origin() (float64, float64)

Origin returns the origin of the map.

func (*Map) Step 

func (m *Map) Step()

Step performs one iteration of the map generation.

func (*Map) Streamlines 

func (m *Map) Streamlines() [][]vectors.Vec2

type MapConfig 

type MapConfig struct {
	SeedRoots func() []*Segment
	Rules     []*SegmentTypeConfig
}

type Node 

type Node struct {
	// contains filtered or unexported fields
}

Node located along any intersection or point along the simplified road polylines.

type NoiseParams 

type NoiseParams struct {
	Seed int64
	// contains filtered or unexported fields
}

type OvalField 

type OvalField struct {
	*BasisField
	Theta float64 // Direction of the major axis
	Ratio float64 // Ratio of the major and minor axis
}

func NewOvalField 

func NewOvalField(centre vectors.Vec2, size, decay, theta, ratio float64) *OvalField

NewOvalField creates a new oval field. NOTE: This tends to create spirals, so use with caution.

func (*OvalField) GetTensor 

func (r *OvalField) GetTensor(point vectors.Vec2) *Tensor

func (*OvalField) GetWeightedTensor 

func (r *OvalField) GetWeightedTensor(point vectors.Vec2, smooth bool) *Tensor

type PolygonFinder 

type PolygonFinder struct {
	Polygons        [][]vectors.Vec2
	ShrunkPolygons  [][]vectors.Vec2
	DividedPolygons [][]vectors.Vec2

	Nodes       []*Node
	Params      PolygonParams
	TensorField *TensorField
	// contains filtered or unexported fields
}

PolygonFinder finds polygons in a graph, used for finding lots and parks.

func NewPolygonFinder 

func NewPolygonFinder(nodes []*Node, params PolygonParams, tensorField *TensorField) *PolygonFinder

func (*PolygonFinder) Divide 

func (p *PolygonFinder) Divide(animate bool)

func (*PolygonFinder) Reset 

func (p *PolygonFinder) Reset()

func (*PolygonFinder) Shrink 

func (p *PolygonFinder) Shrink(animate bool)

Shrink shrinks the polygons by the given amount. Properly shrink polygon so the edges are all the same distance from the road.

func (*PolygonFinder) Update 

func (p *PolygonFinder) Update() bool

type PolygonParams 

type PolygonParams struct {
	MaxLength      int
	MinArea        float64
	ShrinkSpacing  float64
	ChanceNoDivide float64
}

type PolygonUtil 

type PolygonUtil struct {
}

func (*PolygonUtil) InsidePolygon 

func (p *PolygonUtil) InsidePolygon(point vectors.Vec2, polygon []vectors.Vec2) bool

func (*PolygonUtil) PointInRectangle 

func (p *PolygonUtil) PointInRectangle(point vectors.Vec2, origin vectors.Vec2, dimensions vectors.Vec2) bool

func (*PolygonUtil) SliceRectangle 

func (p *PolygonUtil) SliceRectangle(origin, worldDimensions, p1, p2 vectors.Vec2) []vectors.Vec2

SliceRectangle slices a rectangle by line, returning the smallest polygon.

type PriorityQueue 

type PriorityQueue []*Segment

func (PriorityQueue) Len 

func (pq PriorityQueue) Len() int

func (PriorityQueue) Less 

func (pq PriorityQueue) Less(i, j int) bool

func (*PriorityQueue) Pop 

func (pq *PriorityQueue) Pop() interface{}

func (*PriorityQueue) Push 

func (pq *PriorityQueue) Push(x interface{})

func (PriorityQueue) Swap 

func (pq PriorityQueue) Swap(i, j int)

type QuadTree 

type QuadTree interface {
	Add(node ...*Node)
	Remove(node *Node)
	Find(point vectors.Vec2, radius float64) *Node
	Search(point vectors.Vec2, radius float64) []*Node
	All() []*Node
}

type RK4Integrator 

type RK4Integrator struct {
	*FieldIntegrator
	// contains filtered or unexported fields
}

func NewRK4Integrator 

func NewRK4Integrator(field *TensorField, params *StreamlineParams) *RK4Integrator

func (*RK4Integrator) Integrate 

func (r *RK4Integrator) Integrate(point vectors.Vec2, major bool) vectors.Vec2

type RadialField 

type RadialField struct {
	*BasisField
}

func NewRadialField 

func NewRadialField(centre vectors.Vec2, size, decay float64) *RadialField

NewRadialField creates a new radial field.

func (*RadialField) GetTensor 

func (r *RadialField) GetTensor(point vectors.Vec2) *Tensor

func (*RadialField) GetWeightedTensor 

func (r *RadialField) GetWeightedTensor(point vectors.Vec2, smooth bool) *Tensor

type RoadType 

type RoadType int

type Segment 

type Segment struct {
	Point    vectors.Vec2 // end point of the segment
	Length   float64      // length of the segment
	Next     *Segment     // next segment in the same road
	Prev     *Segment     // previous segment in the same road
	Type     RoadType     // type of the segment
	Branches []*Segment   // branches from the same road
	Step     int          // Iteration when this segment was created
	End      bool         // true if this segment is the end of a road
}

Segment is a segment of a road.

func (*Segment) GetVector 

func (s *Segment) GetVector() vectors.Vec2

GetVector returns the vector of the segment.

func (*Segment) Intersects 

func (s *Segment) Intersects(seg *Segment) (bool, vectors.Vec2)

Intersects returns true if the segment intersects with the given segment and the intersection point.

func (*Segment) IsPointOnLine 

func (s *Segment) IsPointOnLine(p vectors.Vec2) bool

IsPointOnLine returns true if the given point is on the line of the segment (within 0.0001)

func (*Segment) Split 

func (s *Segment) Split(p vectors.Vec2) *Segment

Split splits the segment at the given point and returns the new segment.

type SegmentTypeConfig 

type SegmentTypeConfig struct {
	LengthMin            float64 // minimum length of a segment of this type
	LengthVariation      float64 // maximum length variation of a segment of this type (0.1 = 10%)
	AngleMin             float64 // minimum angle of a segment extension in degrees (10.0 = 10°)
	AngleVariance        float64 // maximum angle variation of a segment extension in degrees (10.0 = 10°)
	AngleReversal        bool    // allow reverse angle of the road
	BranchingChance      float64 // chance of branching (0.1 = 10%)
	BranchingAngle       float64 // angle of subbranches in degrees (10.0 = 10°)
	BranchingReversal    bool    // allow reverse branching direction of the road
	BranchSameType       bool    // allow branching to the same type of road
	BranchSameTypeChance float64 // chance of branching to the same type of road (0.1 = 10%)
}

SegmentTypeConfig is the configuration for a segment type.

type StreamlineGenerator 

type StreamlineGenerator struct {
	SEED_AT_ENDPOINTS bool
	NEAR_EDGE         int // Sample near edge
	// contains filtered or unexported fields
}

func NewStreamlineGenerator 

func NewStreamlineGenerator(seed int64, integrator FieldIntegratorIf, origin, worldDimensions vectors.Vec2, params *StreamlineParams) (*StreamlineGenerator, error)

func (*StreamlineGenerator) ClearStreamlines 

func (sg *StreamlineGenerator) ClearStreamlines()

func (*StreamlineGenerator) ExportToSVG 

func (sg *StreamlineGenerator) ExportToSVG(filename string) error

ExportToSVG exports the streamlines to an SVG file.

type StreamlineIntegration 

type StreamlineIntegration struct {
	Seed          vectors.Vec2
	OriginalDir   vectors.Vec2
	PreviousDir   vectors.Vec2
	PreviousPoint vectors.Vec2
	Streamline    []vectors.Vec2
	Valid         bool
}

type StreamlineParams 

type StreamlineParams struct {
	Dsep              float64 // Streamline seed separating distance
	Dtest             float64 // Streamline integration separating distance
	Dstep             float64 // Step size
	Dcirclejoin       float64 // How far to look to join circles - (e.g. 2 x dstep)
	Dlookahead        float64 // How far to look ahead to join up dangling
	Joinangle         float64 // Angle to join roads in radians
	PathIterations    int     // Path integration iteration limit
	SeedTries         int     // Max failed seeds
	SimplifyTolerance float64
	CollideEarly      float64 // Chance of early collision 0-1
}

type Tensor 

type Tensor struct {
	// contains filtered or unexported fields
}

Tensor represents a tensor used for generating a city map. Represent the matrix as a 2 element list [ 0, 1 , 1, -0 ]

func (*Tensor) Scale 

func (t *Tensor) Scale(s float64) *Tensor

type TensorField 

type TensorField struct {
	// contains filtered or unexported fields
}

func NewTensorField 

func NewTensorField(n *NoiseParams) *TensorField

NewTensorField creates a new tensor field.

func (*TensorField) AddGrid 

func (t *TensorField) AddGrid(centre vectors.Vec2, size float64, decay float64, theta float64)

func (*TensorField) AddRadial 

func (t *TensorField) AddRadial(centre vectors.Vec2, size float64, decay float64)

type TotalTensorThing 

type TotalTensorThing struct {
	// contains filtered or unexported fields
}

func TensorTest 

func TensorTest() (*TotalTensorThing, error)

func (*TotalTensorThing) ExportToPNG 

func (t *TotalTensorThing) ExportToPNG(filename string) error

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.