A Trig-less Line of Sight Algorithm in Two Dimensions

Overview

A Trig-less Line of Sight Algorithm in Two Dimensions

In many examples of 2D line-of-sight algorithms, expensive operations like trigonometry are used. Additionally, some methods have intentional inaccuracies in them for the sake of simplicity. Here, we give an algorithm which does not fudge the numbers, and uses only basic arithmetic: addition, subtraction, multiplication, and division. This is not intended to replace the existing algorithms, or even be more efficient in practice.

The algorithm is implemented in Rust. The repo contains a simple example application written using ggez in addition to the algorithm itself, which can be downloaded and run by cloning the repo and using cargo. main.rs contains the code for the application, sight.rs contains the line of sight algorithm, and space.rs contains the structures and helper methods necessary to make it work.

I encourage you to check out the book available here: https://basstabs.github.io/2d-line-of-sight/

It walks through the math behind making the algorithm work and includes plenty of visual diagrams to help explain it. Hopefully, it is more enlightening than just reading the code. It also includes references to some of the other excellent articles on this subject available on the web.

You might also like...
 Example of a genetic algorithm in Rust and Python
Example of a genetic algorithm in Rust and Python

Example of a genetic algorithm in Rust and Python Monkey typewriter Finding the phrase 'To be or not to be. That is the question.' Inspired by the exa

A simple implementation of the astar pathfinding algorithm from red blob games
A simple implementation of the astar pathfinding algorithm from red blob games

A simple implementation of the astar pathfinding algorithm from red blob games. In order to use the pathfinder you must have a path map for it to navi

A Rust implementation of the AGCWD algorithm

AGCWD is described in the paper "Efficient Contrast Enhancement Using Adaptive Gamma Correction With Weighting Distribution".

hubpack is an algorithm for converting Rust values to bytes and back.

hubpack is an algorithm for converting Rust values to bytes and back. It was originally designed for encoding messages sent between embedded programs. It is designed for use with serde.

nsga is an opinionated implementation of the NSGA-II (Non-dominated Sorting Genetic Algorithm)

nsga nsga is an opinionated implementation of the NSGA-II (Non-dominated Sorting Genetic Algorithm), a multi-objective genetic optimization algorithm.

Library that implements different versions of PPMD algorithm (compress and decompress)

ppmd-rs Library that implements different versions of PPMD algorithm (compress and decompress) Dependencies Rust 1.58 or newer Cargo How to build Clon

Online algorithm for mean and variance, with support for uneven weights

welford Online algorithm for mean and variance, with support for uneven weights. This implements the Welford's online algorithm for computing mean and

This repository simulates and renders fluid particles in two dimensions, in Rust.

mlsmpm-particles-rs This repository simulates and renders fluid particles in two dimensions, in Rust. My matching implementation in Go is mlsmpm-parti

A Platform-less, Runtime-less Actor Computing Model

CrossBus A Platform-Less, Runtime-Less Actor Computing Model Overview CrossBus is an implementation of Actor Computing Model, with the concept that Ru

This code generate coinjoin transaction whici has two inputs and two outputs

How to create coinjoin transaction This code generate coinjoin transaction whici has two inputs and two outputs. First, we create two trasactions. The

Suite for automatically testing algorithm questions from the Polish Algorithm Olympiad.

oisuite Your number #1 tool to managing your algo questions! This software only works on UNIX-based operating systems (macOS, Linux, BSD, etc.) Projec

Improve and strengthen your strings by making them strongly-typed with less boilerplate

aliri_braid Improve and strengthen your strings Strongly-typed APIs reduce errors and confusion over passing around un-typed strings.

eJNI is a Rust crate to make working with Java's JNI less painful by providing abstractions.

eJNI provides abstractions for often-used classes from the Java standard library, like Map and List. Besides this eJNI also provides easy ways to work with Java's primitives and their object counterparts (e.g int and Integer).

🦔 Fast, lightweight & schema-less search backend. An alternative to Elasticsearch that runs on a few MBs of RAM.
🦔 Fast, lightweight & schema-less search backend. An alternative to Elasticsearch that runs on a few MBs of RAM.

🦔 Fast, lightweight & schema-less search backend. An alternative to Elasticsearch that runs on a few MBs of RAM.

⏳ trackie is a private, daemon-less time tracker for your CLI.
⏳ trackie is a private, daemon-less time tracker for your CLI.

⏳ trackie `trackie` is a private, daemon-less time tracker running in your CLI. Trackie offers an easy CLI to track the time you spent on your various

Work-in-progress Nintendo Switch emulator, written in Rust and slightly less focused on gaming

pegasus Work-in-progress Nintendo Switch emulator, written in pure Rust and slightly less focused on gaming Information This project aims to be a diff

This project aims to implement a CSS(less like) parser in rust. Currently the code is targeting the PostCSS AST.

CSS(less like) parser written in rust (WIP) This project aims to implement a CSS(less like) parser in rust. Currently the code is targeting the PostCS

This project aims to implement a CSS(less like) parser in rust. Currently the code is targeting the PostCSS AST. Very early stage, do not use in production.

CSS(less like) parser written in rust (WIP) This project aims to implement a CSS(less like) parser in rust. Currently the code is targeting the PostCS

Comments
  • Great tutorial!

    Great tutorial!

    Nice work here. Apologies for using your issue tracker as a contact form, but I couldn’t find another way to reach out. I was wondering if you might be interested in a paid writing gig. You’ll find my contact details in my profile.

    opened by erlend-sh 0
Owner
null
Compute a pairwise SNP distance matrix from one or two alignment(s)

Compute a pairwise SNP distance matrix from one or two alignment(s) Table of Contents Motivation Install cargo conda Precompiled binaries homebrew Con

Michael Hall 11 Nov 2, 2022
Execute genetic algorithm (GA) simulations in a customizable and extensible way.

genevo genevo provides building blocks to run simulations of optimization and search problems using genetic algorithms (GA). The vision for genevo is

Innoave 110 Dec 21, 2022
Genetic Algorithm library in Rust

RsGenetic Summary and Features RsGenetic is a framework for executing genetic algorithms in Rust. It is designed to have a simple but modular API. Exa

Mathieu De Coster 74 Dec 27, 2022
A SIMD-accelerated Adler-32 rolling hash algorithm implementation.

simd-adler32 A SIMD-accelerated Adler-32 rolling hash algorithm implementation. Features No dependencies Support no_std (with default-features = false

Marvin Countryman 23 Dec 19, 2022
Rust implementation of AstroBWT Proof-Of-Work algorithm

AstroBWT AstroBWT is a proof-of-work (PoW) algorithm based on Burrows-Wheeler transform (BWT). Developed and used by the DERO Project for Mobile (arm)

null 6 Mar 7, 2022
An implementation of the A-Star pathfinding algorithm tailored for traversing a bespoke collection of weighted hexagons.

An implementation of the A-Star pathfinding algorithm tailored for traversing a bespoke collection of weighted hexagons. It's intended to calculate the most optimal path to a target hexagon where you are traversing from the centre of one hexagon to the next along a line orthogonal to a hexagon edge

null 19 Dec 11, 2022
The labs of Raft consensus algorithm based on MadSim.

MadRaft The labs of Raft consensus algorithm based on MadSim. Some codes are derived from MIT 6.824 and PingCAP Talent Plan: Raft Lab. Thanks for thei

MadSys Research Group 48 Dec 28, 2022
Pure Rust implementation of the Double Ratchet algorithm

Double Ratchet A pure Rust implementation of the Double Ratchet, as specified by Trevor Perrin and Moxie Marlinspike. The Double Ratchet allows two us

Sebastian 52 Nov 25, 2022
A rust implementation of Alexey Akhunov's multiproof algorithm

multiproof.rs A rust implementation of Alexey Akhunov's multiproof algorithm. At the time of creation, multiproof is still a work in progress and this

Guillaume Ballet 30 Aug 24, 2022
Maximum Relevance - Minimum redundancy feature selection algorithm

mrmr Maximum Relevance - Minimum redundancy feature selection algorithm implemented in Rust. Usage CLI app. It gets input from a csv dataset with head

Jorge 2 Jan 1, 2022