Golang implementation of the Optimal Reciprocal Collision Avoidance (ORCA) algorithm

Overview

go-orca

Golang implementation of the Optimal Reciprocal Collision Avoidance (ORCA) algorithm

Disclaimer

This project is under active development and is not yet feature complete, and may contain bugs. We welcome contributions in the form of new issues and pull requests.

This project was created after endlessly consulting the canonical implementation github.com/snape/RVO2 and follows the general shape of the reference. General improvements lie in abstracting away some code and documenting a number of assumptions the reference implementation makes.

Background

ORCA is useful for local collision avoidance in large systems. This repository aims to be an implementation of the ORCA algorithm with much improved documentation and API.

More prosaic documentation of this library will be made available at blog.downflux.com soon.

Installation

go version
> go version go1.17.4 linux/amd64

Updating

go get -u ./...
go mod tidy

Demo

go run \
  demo/generator/main.go --mode=grid | go run \
  demo/main.go --frames=1250 > demo.gif

ORCA demo

Here, we have 250 agents of random size and speeds travelling in 2D ambient space to some random nearby destination.

Profiling

N.B.: WSL does not profile correctly. See golang/go#22366.

go test -v \
  github.com/downflux/go-orca/... \
  -bench . \
  -benchmem -cpu 1,2,4,8,16,32,64

go test -v \
  github.com/downflux/go-orca/orca \
  -bench BenchmarkStep/N=1000000 \
  -benchmem \
  -cpuprofile cpu.out
  -memprofile mem.out

go tool pprof -tree -nodecount=10 cpu.out

See pprof for more information.

Sample Metrics

$ go test github.com/downflux/go-orca/orca -bench .
goos: linux
goarch: amd64
pkg: github.com/downflux/go-orca/orca
cpu: Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz
BenchmarkStep/Size=1/N=1000-8                224           5291836 ns/op
BenchmarkStep/Size=2/N=1000-8                388           3168457 ns/op
BenchmarkStep/Size=4/N=1000-8                508           2633228 ns/op
BenchmarkStep/Size=8/N=1000-8                576           2321055 ns/op
BenchmarkStep/Size=16/N=1000-8               693           2004639 ns/op
BenchmarkStep/Size=32/N=1000-8               730           1948345 ns/op
BenchmarkStep/Size=64/N=1000-8               705           1974854 ns/op
BenchmarkStep/Size=1/N=10000-8                 7         171990286 ns/op
BenchmarkStep/Size=2/N=10000-8                 9         112703811 ns/op
BenchmarkStep/Size=4/N=10000-8                19          75218658 ns/op
BenchmarkStep/Size=8/N=10000-8                19          66837863 ns/op
BenchmarkStep/Size=16/N=10000-8               24          67420958 ns/op
BenchmarkStep/Size=32/N=10000-8               32          59837678 ns/op
BenchmarkStep/Size=64/N=10000-8               24          58414696 ns/op
BenchmarkStep/Size=1/N=100000-8                1        32582184800 ns/op
BenchmarkStep/Size=2/N=100000-8                1        19468817500 ns/op
BenchmarkStep/Size=4/N=100000-8                1        12772734100 ns/op
BenchmarkStep/Size=8/N=100000-8                1        10489621800 ns/op
BenchmarkStep/Size=16/N=100000-8               1        10855534900 ns/op
BenchmarkStep/Size=32/N=100000-8               1        10736456000 ns/op
BenchmarkStep/Size=64/N=100000-8               1        10513208500 ns/op
PASS
ok      github.com/downflux/go-orca/orca        139.516s

Performance

Performance metrics shoud be compared against Granberg, Snape et al., and van den Berg et al.. We estimate that there is about another 50% optimization achievable in the current implementation of the ORCA algorithm.

TODO

We have not yet implemented generating velocity objects for polygonal obstacles. The current implementation only adjusts trajectory for other circular agents.

You might also like...
Optimal implementation of ordered maps for Golang - ie maps that remember the order in which keys were inserted.

Goland Ordered Maps Same as regular maps, but also remembers the order in which keys were inserted, akin to Python's collections.OrderedDicts. It offe

Eunomia is a distributed application framework that support Gossip protocol, QuorumNWR algorithm, PBFT algorithm, PoW algorithm, and ZAB protocol and so on.

Introduction Eunomia is a distributed application framework that facilitates developers to quickly develop distributed applications and supports distr

An optimal, byte-aligned, LZ+RLE hybrid encoder, designed to maximize decoding speed on NMOS 6502 and derived CPUs
An optimal, byte-aligned, LZ+RLE hybrid encoder, designed to maximize decoding speed on NMOS 6502 and derived CPUs

TSCrunch TSCrunch is an optimal, byte-aligned, LZ+RLE hybrid encoder, designed to maximize decoding speed on NMOS 6502 and derived CPUs, while keeping

Go-enum-algorithm - Implement an enumeration algorithm in GO

go-enum-algorithm implement an enumeration algorithm in GO run the code go run m

Golang implementation of the Paice/Husk Stemming Algorithm

##Golang Implementation of the Paice/Husk stemming algorithm This project was created for the QUT course INB344. Details on the algorithm can be found

Golang implementation of the Paice/Husk Stemming Algorithm

##Golang Implementation of the Paice/Husk stemming algorithm This project was created for the QUT course INB344. Details on the algorithm can be found

Golang implementation of Sliding Window Algorithm for distributed rate limiting.
Golang implementation of Sliding Window Algorithm for distributed rate limiting.

slidingwindow Golang implementation of Sliding Window Algorithm for distributed rate limiting. Installation $ go get -u github.com/RussellLuo/slidingw

Ratelimit - This package provides a Golang implementation of the leaky-bucket rate limit algorithm

Go rate limiter This package provides a Golang implementation of the leaky-bucke

Go implementation of the A* search algorithm

go-astar A* pathfinding implementation for Go The A* pathfinding algorithm is a pathfinding algorithm noted for its performance and accuracy and is co

A native Go clean room implementation of the Porter Stemming algorithm.

Go Porter Stemmer A native Go clean room implementation of the Porter Stemming Algorithm. This algorithm is of interest to people doing Machine Learni

Go implementation of the bspatch algorithm

binarydist Package binarydist implements binary diff and patch as described on http://www.daemonology.net/bsdiff/. It reads and writes files compatibl

Fast (linear time) implementation of the Gaussian Blur algorithm in Go.
Fast (linear time) implementation of the Gaussian Blur algorithm in Go.

Song2 Fast (linear time) implementation of the Gaussian Blur algorithm in Go.

A Go implementation of the 64-bit xxHash algorithm (XXH64)

xxhash xxhash is a Go implementation of the 64-bit xxHash algorithm, XXH64. This is a high-quality hashing algorithm that is much faster than anything

Implementation of Boyer-Moore fast string search algorithm in Go

boyermoore Implementation of Boyer-Moore fast string search algorithm in Go

k-means clustering algorithm implementation written in Go
k-means clustering algorithm implementation written in Go

kmeans k-means clustering algorithm implementation written in Go What It Does k-means clustering partitions a multi-dimensional data set into k cluste

A Go implementation of the core algorithm in paper Indexing Boolean Expression

Boolean Expression Indexer Go library A Go implementation of the core algorithm in paper Indexing Boolean Expression, which already supports the fol

Go implementation of the JWZ email threading algorithm
Go implementation of the JWZ email threading algorithm

The JWZ Threading algorithm written in Go This is an open source Go implementation of the widely known JWZ message threading algorithm originally writ

A faster RWLock primitive in Go, 2-3 times faster than RWMutex. A Go implementation of concurrency control algorithm in paper Left-Right - A Concurrency Control Technique with Wait-Free Population Oblivious Reads

Go Left Right Concurrency A Go implementation of the left-right concurrency control algorithm in paper Left-Right - A Concurrency Control Technique w

Go implementation of Donald Knuth's Algorithm 7.2.2.1C for exact cover with colors.

go-dlx Go implementation of Donald Knuth's Algorithm 7.2.2.1C for exact cover with colors. This code is based on the Algorithm C described in http://w

Releases(v0.3.0)
  • v0.3.0(Jun 19, 2022)

    What's Changed

    • Fix 3D solver returning infeasible solutions causing collisions by @minkezhang in https://github.com/downflux/go-orca/pull/4
    • Update wall VO to conform to RVO2 implementation by @minkezhang in https://github.com/downflux/go-orca/pull/5
    • Fix conformance tests for wall segment VO by @minkezhang in https://github.com/downflux/go-orca/pull/6
    • Refactor VO tests by @minkezhang in https://github.com/downflux/go-orca/pull/7

    Full Changelog: https://github.com/downflux/go-orca/compare/v0.2.0...v0.3.0

    Source code(tar.gz)
    Source code(zip)
  • v0.2.0(Dec 16, 2021)

  • v0.1.4(Dec 15, 2021)

  • v0.1.3(Dec 14, 2021)

  • v0.1.2(Dec 13, 2021)

  • v0.1.1(Dec 11, 2021)

  • v0.1.0(Dec 11, 2021)

A lightweight UUID implementation

uuid uuid is a lightweight implementation for Univerally unique identifier. Usage var id UUID = uuid.Rand() fmt.Println(id.Hex()) fmt.Println(id.Raw()

Steven Luu 53 Feb 25, 2020
An extremely fast UUID alternative written in golang

Overview WUID is a globally unique number generator, while it is NOT a UUID implementation. WUID is 10-135 times faster than UUID and 4600 times faste

Edwin 481 Dec 9, 2022
An extremely fast UUID alternative written in golang

Overview WUID is a globally unique number generator, while it is NOT a UUID implementation. WUID is 10-135 times faster than UUID and 4600 times faste

Edwin 11 May 10, 2021
A simple to use Go (golang) package to generate or parse Twitter snowflake IDs

snowflake snowflake is a Go package that provides A very simple Twitter snowflake generator. Methods to parse existing snowflake IDs. Methods to conve

null 2.3k Dec 30, 2022
✨ Generate unique IDs (Port of Node package "generate-snowflake" to Golang)

✨ Generate Snowflake Generate unique IDs. Inspired by Twitter's Snowflake system. ?? Installation Initialize your project (go mod init example.com/exa

Barış DEMİRCİ 6 Feb 11, 2022
Golang wrapper for the Snowflake Api.

GoSnowflakeApi GoSnowflakeApi is an api wrapper for the snowflake api written in golang for golang developers. Example package main import ( "fmt

SnowflakeDev Community 4 Jul 25, 2021
Snowflake implemented in GO (Golang)

snowflake Snowflake is a fast, goroutine-safe unique ID generator built for distributed systems Key concepts Snowflake Snowflakes are int64s. uint64 i

Jacques Amsel 4 Oct 27, 2022
UUID package for Golang

UUID package for Go language This package provides pure Go implementation of Universally Unique Identifier (UUID). Supported both creation and parsing

Maxim Bublis 4.4k Dec 9, 2021
Snowflake - A simple to use Go (golang) package to generate or parse Twitter snowflake IDs

❄️ Go-Snowflake A Snowflake Generator for Go A simple to use Go (golang) package

houseme 7 Oct 20, 2022
Modify orca-zhang/borm in order to use in PostgreSQL

borm ??️ 针对 orca-zhang/borm 进行了修改,暂时只能兼容PostgreSQL 原因 在b站时候用过borm,用起来感觉非常简洁 自己学校里用PostgreSQL比较多 可变条件真的非常好用 问题 首先需要注意的是,这是写给PG的 PG 根本不存在某些 MySQL 独有的函数

null 14 Aug 24, 2022