Efficient Raycasting for 2d Tilemaps

Java implemetation of the approximate ray/beam casting algorithm for a discrete 2D tilemaps.

WUT?

For a square 2D map that consists of tiles (NxN tiles), where each tile can be either empty, or contain light source or obstacle, this algorithm calculates approximate brightness of each tile, taking into account positions of the light sources and occlusion from the obstacles.

(image was generated with LightingTest)

See also:

• JS demo
• More detailed description by Kevin Granade

Properties

If the input field is NxN tiles:

• worst case O(N³) (for the number of light sources between N and N²)
• best case is O(N²) (for constant number of light sources)
• CPU cache friednly (all data structures are accessed sequentially)

Why?

Naive ray/shadowcasting implementation is O(N⁴) in worst case (O(N²) for each of O(N²) light sources). This algorithm is O(N³) worst case (and it really matters when N >= 100).

Performance

See benchmarks.

Building and Running

Maven is used for building. Java 8 is a prerequisite.

• Build and run tests: ./mvnw clean install assembly:single
• Run Lighting benchmarks after build: java -jar target/raycasting-2d-java-1.0-SNAPSHOT-jar-with-dependencies.jar

Project Structure

• Lighting.java Class that implements the lighting calculation
• LightingBenchmark.java JMH benchmark for lighting
• Rotation.java Utility class for matrix rotations
• RotationBenchmark.java Rotations benchmark
• LightingTest.java Simple unit test for lighting. Additionally generates PNG with the results.

License

Copyright © 2018 Ivan Zaitsev (https://github.com/Aivean/efficient-2d-raycasting)