barneshut

package
v0.0.0-...-1bee6ba Latest Latest
Warning

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

 Go to latest Published: Nov 21, 2021 License: MIT Imports: 24 Imported by: 0

Documentation

Overview

Package barnes-hut is a modified barnes-hut simulation algorithm witg concurrent computation.

A the start of the simulation, bodies are spread according to the density of the country of interest. At the end of the simulation, bodies are spread evenly on a 2D rectangle. At the end of the simulation, the body repartition is said to be hyperuniform (https://www.quantamagazine.org/hyperuniformity-found-in-birds-math-and-physics-20160712/)

Barnes-Hut is an embarisgly parallel algorithm. This implementation is used the concurrent model of the go langage. Nb of conurrent routine can be set up dynamicaly.

TKV implementation starts from a Barnes-Hut implementation of the gravitation simulation and make the following modification:

In a gravitational simulation, bodies are attracted to each others by mean of the newtownian gravitation law. Here, repulsion is used instead of gravitational attraction. A drag is introduced to put simulation bodies to rest (see #Run.UpdateVelocity)

In a cosmological simulation, bodies position are not limited. Here, bodies are kept within a [0;1]*[0;1] square by having "mirror" bodies that forbids a body from crossing the border (see #Run.UpdatePosition)

Index

Constants

View Source 
const (
	NbPaletteGrays = 100
	Padding        = 4
)
View Source 
const (
	AUTO   = "AUTO"
	MANUAL = "MANUAL"
)

Possible values for DtAdjustModeType

View Source 
const (
	STOPPED = "STOPPED"
	RUNNING = "RUNNING"
)

Possible values for simulation State

View Source 
const (
	WITHOUT_BORDERS = "WITHOUT_BORDERS"
	WITH_BORDERS    = "WITH_BORDERS"
)

Possible values for RenderState

View Source 
const (
	ORIGINAL_CONFIGURATION = "ORIGINAL_CONFIGURATION"
	RUNNING_CONFIGURATION  = "RUNNING_CONFIGURATION"
)

Possible values for RenderChoice

View Source 
const (
	CountryBodiesGifNamePattern = "conf-%s-%08d-%05d.gif"
)
View Source 
const (
	CountryBodiesNamePattern = "conf-%s-%08d-%05d.bods"
)
View Source 
const (
	CountryBodiesSVGNamePattern = "conf-%s-%08d-%05d.svg"
)

Variables

View Source 
var (
	Trace   *log.Logger // debug Level
	Info    *log.Logger // debug Level
	Warning *log.Logger // debug Level
	Error   *log.Logger // debug Level
)
View Source 
var BN_THETA float64 = 0.5

BN_THETA is the barnes hut criteria If distance to Center Of Mass (COM) of the box is more than BN_THETA * side of the box then, compute force from the whole box instead computing for each node of the box.

View Source 
var BN_THETA_Request = BN_THETA

New value of theta requested by the UI. The real BN_THETA will be changed at the end of the current step.

View Source 
var ConcurrentRoutines int = 100

set the number of concurrent routine for the physic calculation this value can be set interactively during the run

View Source 
var CurrentCountry = "bods"
View Source 
var CutoffDistance float64 = 1.0

Cutoff for influence. According to Bartolo, 1/r2 is very strong on a plane (integration does not convergence on the plane) therefore a cutoff distance for the computation of the force is wellcome first try at 1/10 th

View Source 
var Dt float64 = 2.3 * 1e-10 // difficult to fine tune

var Dt float64 = 3*1e-8 // difficult to fine tune

View Source 
var DtRequest = Dt // new value of Dt requested by the UI. The real Dt will be changed at the end of the current step.
View Source 
var ETA float64 = 0.0

constant to be added to the distance between bodies in order to compute repulsion (avoid near infinite repulsion force) note : declaring those variable as constant has no impact on benchmarks results var ETA float64 = 1e-10

View Source 
var G float64 = 0.01

pseudo gravitational constant to compute should have no effect on the simulation since Dt is computed according to computed acceleration

View Source 
var Gflops float64
View Source 
var MaxDisplacement float64 = 0.001 // cannot make more that 1/1000 th of the unit square per second

velocity cannot be too high in order to stop bodies from overtaking each others. The variable defines when displacement has to be capped

View Source 
var MaxRatioDisplacement float64 = 0.5

give the theorical max displacement, as a ratio between the min distance and the max speed note: 2.0 gives too much stirring

View Source 
var NbOfNeighboursPerBody int = 10

the measure of stirring is computed with a finite number of neighbours no stirring is that the neighbours at the end of the run are the same neighbours that at the beginning

View Source 
var ShutdownCriteria float64 = 0.00001

At what step do the simulation stop

View Source 
var SpeedDragFactor float64 = 0.2

how much drag we put (1.0 is no drag) tHis criteria is important because it favors bodies that moves freely against bodies that are stuck on a border 0.99 makes a very bumpy behavior for the Dt

View Source 
var StepDuration float64
View Source 
var UseBarnesHut bool = true

if true, Barnes-Hut algo is used

Functions

func Init 

func Init(
	traceHandle io.Writer,
	infoHandle io.Writer,
	warningHandle io.Writer,
	errorHandle io.Writer)

Function Init inits trace

func NbVillagePerAxe 

func NbVillagePerAxe() int

func SetNbRoutines 

func SetNbRoutines(nbRoutines_p int)

func SetNbVillagePerAxe 

func SetNbVillagePerAxe(nbVillagePerAxe_p int)

func SetRatioBorderBodies 

func SetRatioBorderBodies(ratioOfBorderVillages_p float64)

func SpreadOnCircle 

func SpreadOnCircle(bodies *[]quadtree.Body)

function used to spread bodies randomly on the unit square

Types

type Acc 

type Acc struct {
	X float64
	Y float64
}

Acceleration

type Body 

type Body struct {
	quadtree.Body
}

type DtAdjustModeType 

type DtAdjustModeType string

decides wether Dt is set manual or automaticaly 

var DtAdjustMode DtAdjustModeType

type MaxRepulsiveForce 

type MaxRepulsiveForce struct {
	AccX, AccY, X, Y float64
	Norm             float64 // direction and norm
	Idx              int     // body index where repulsive vector is max
}

type Neighbour 

type Neighbour struct {
	Distance float64
	// contains filtered or unexported fields
}

relative to a body of interest, the storage for a neighbour with its distance nota : this is used to measure the stirring of the bodies along the simulation

type NeighbourDico 

type NeighbourDico [][]Neighbour

func (*NeighbourDico) Check 

func (dico *NeighbourDico) Check()

check integrity not twice the same neighbor

func (*NeighbourDico) ComputeRatioOfNilNeighbours 

func (dico *NeighbourDico) ComputeRatioOfNilNeighbours() float64

func (*NeighbourDico) ComputeStirring 

func (dico *NeighbourDico) ComputeStirring(dicoOrig *NeighbourDico) float64

compute stirring parse all bodies and count the number of neighbors that are still the neighbours at the origin

func (*NeighbourDico) Copy 

func (dicoTarget *NeighbourDico) Copy(dicoSource *NeighbourDico)

reset neighbour dico

func (*NeighbourDico) Insert 

func (dico *NeighbourDico) Insert(index int, body *quadtree.Body, distance float64)

insert body at index in the dico according to the distance

func (*NeighbourDico) Reset 

func (dico *NeighbourDico) Reset()

reset neighbour dico

type Pos 

type Pos struct {
	X float64
	Y float64
}

Bodies's X,Y position coordinates are float64 between 0 & 1

type RenderChoice 

type RenderChoice string

decide wether to display the original configuration or the running configruation

type RenderState 

type RenderState string

decide wether, villages borders are drawn

type RepulsionField 

type RepulsionField struct {
	XMin, YMin, XMax, YMax float64 // coordinate of the rendering area
	GridFieldTicks         int     // nb of intervals where the field is computed
	// contains filtered or unexported fields
}

a RepulsionField stores the computation of a scalar field with the values of the repulsion field (1/r) on a fixed area, at interpolation points ( GridFieldTicks interpolation points per dimension ) this structure is transcient

func NewRepulsionField 

func NewRepulsionField(XMin, YMin, XMax, YMax float64, GridFieldTicks int, q *quadtree.Quadtree, cutoff float64) *RepulsionField

func (*RepulsionField) ComputeField 

func (f *RepulsionField) ComputeField()

compute field for all interpolation points concurrently

func (*RepulsionField) ComputeFieldRecursive 

func (f *RepulsionField) ComputeFieldRecursive(x, y float64, q *quadtree.Quadtree, coord quadtree.Coord, v *float64)

compute repulsion field at interpolation point x, y and update v

func (*RepulsionField) XY 

func (f *RepulsionField) XY(i, j int) (x, y float64)

compute x,y coordinates in the square from the i,j coordinate in the field

type Run 

type Run struct {
	OutputDir     string // output dir for the run
	StatusFileLog *os.File

	CaptureGifStep int // simulaton steps between gif generation
	// contains filtered or unexported fields
}

a simulation run

func NewRun 

func NewRun() *Run

func (*Run) BodyCountGini 

func (r *Run) BodyCountGini() quadtree.QuadtreeGini

func (*Run) CaptureConfig 

func (r *Run) CaptureConfig() bool

serialize bodies's state vector into a file convention is "step-xxxx.bod" return true if operation was successful works only if state is STOPPED

func (*Run) CaptureConfigBase64 

func (r *Run) CaptureConfigBase64() bool

func (*Run) CaptureGif 

func (r *Run) CaptureGif() bool

func (*Run) CaptureSVG 

func (r *Run) CaptureSVG() bool

func (*Run) ComputeDensityTencilePerTerritory 

func (r *Run) ComputeDensityTencilePerTerritory() [10]float64

func (*Run) ComputeDensityTencilePerTerritoryString 

func (r *Run) ComputeDensityTencilePerTerritoryString() [10]string

compute the density per village and return the density per village

func (*Run) ComputeMaxRepulsiveForce 

func (r *Run) ComputeMaxRepulsiveForce()

func (*Run) ComputeRepulsiveForce 

func (r *Run) ComputeRepulsiveForce()

compute repulsive forces

func (*Run) ComputeRepulsiveForceConcurrent 

func (r *Run) ComputeRepulsiveForceConcurrent(nbRoutine int) float64

compute repulsive forces by spreading the calculus among nbRoutine go routines

return minInterbodyDistance

func (*Run) ComputeRepulsiveForceSubSet 

func (r *Run) ComputeRepulsiveForceSubSet(startIndex, endIndex int) float64

compute repulsive forces for a sub part of the bodies return the minimal distance between the bodies sub set

func (*Run) ComputeRepulsiveForceSubSetMinDist 

func (r *Run) ComputeRepulsiveForceSubSetMinDist(startIndex, endIndex int, minInterbodyDistanceChan chan<- float64)

compute repulsive forces for a sub part of the bodies

send the computed min distance through minInterbodyDistanceChan

func (*Run) CreateMovieFromGif 

func (r *Run) CreateMovieFromGif()

parse and concenate all gif file into an animated movie

func (*Run) DirConfig 

func (r *Run) DirConfig() []string

return the list of available configuration

func (*Run) GetMaxRepulsiveForce 

func (r *Run) GetMaxRepulsiveForce() MaxRepulsiveForce

func (*Run) GetMinInterBodyDistance 

func (r *Run) GetMinInterBodyDistance() float64

func (*Run) GetStep 

func (r *Run) GetStep() int

func (*Run) GiniOverTime 

func (r *Run) GiniOverTime() [][]float64

func (*Run) GiniOverTimeTransposed 

func (r *Run) GiniOverTimeTransposed() [][]float64

func (*Run) Init 

func (r *Run) Init(bodies *([]quadtree.Body))

init the run with an array of quadtree bodies

func (*Run) InitNeighbourDico 

func (r *Run) InitNeighbourDico(bodies *([]quadtree.Body))

func (*Run) LoadConfig 

func (r *Run) LoadConfig(path string, filename string) bool

load configuration from filename (does not contain path) works only if state is STOPPED

func (*Run) LoadConfigOrig 

func (r *Run) LoadConfigOrig(filename string) bool

load configuration from filename into the original config (for computing borders) works only if state is STOPPED

func (*Run) OneStep 

func (r *Run) OneStep()

func (*Run) OneStepOptional 

func (r *Run) OneStepOptional(updatePosition bool)

func (*Run) RatioOfBodiesWithCapVel 

func (r *Run) RatioOfBodiesWithCapVel() float64

func (*Run) RenderGif 

func (r *Run) RenderGif(out io.Writer, encode64 bool)

RenderGif creates a gif image and serialize it into out if encode64 is true, the serialization is encoded in base 64 (64 ASCII characters), enabling transmission over http

func (*Run) RenderSVG 

func (r *Run) RenderSVG(out io.Writer)

func (*Run) RunSimulation 

func (r *Run) RunSimulation()

RunSimulation is the main entry to the simulation It call for one step of simulation until the energy decrease ratio is met

func (*Run) SetCountry 

func (r *Run) SetCountry(country string)

func (*Run) SetGridFieldNb 

func (r *Run) SetGridFieldNb(v int)

func (*Run) SetRenderingWindow 

func (r *Run) SetRenderingWindow(xMin, xMax, yMin, yMax float64)

func (*Run) SetState 

func (r *Run) SetState(s State)

func (*Run) State 

func (r *Run) State() State

func (*Run) Status 

func (r *Run) Status() string

func (*Run) ToggleFieldRendering 

func (r *Run) ToggleFieldRendering()

func (*Run) ToggleManualAuto 

func (r *Run) ToggleManualAuto()

func (*Run) ToggleRenderChoice 

func (r *Run) ToggleRenderChoice()

func (*Run) UpdatePosition 

func (r *Run) UpdatePosition()

func (*Run) UpdateVelocity 

func (r *Run) UpdateVelocity()

type State 

type State string

state of the simulation

type Vel 

type Vel struct {
	X float64
	Y float64
}

Velocity

Source Files

View all Source files

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.