branchless-cardinal-direction-movement/README.md at main · AbidiHichem-TunisianCoder/branchless-cardinal-direction-movement · GitHub
//blob/show" data-turbo-transient="true" />
Skip to content
Search or jump to...
Search code, repositories, users, issues, pull requests...
-->
Search
Clear
Search syntax tips
Provide feedback
--><br>We read every piece of feedback, and take your input very seriously.
Include my email address so I can be contacted
Cancel
Submit feedback
Saved searches
Use saved searches to filter your results more quickly
-->
Name
Query
To see all available qualifiers, see our documentation.
Cancel
Create saved search
Sign in
//blob/show;ref_cta:Sign up;ref_loc:header logged out"}"<br>Sign up
Appearance settings
Resetting focus
You signed in with another tab or window. Reload to refresh your session.<br>You signed out in another tab or window. Reload to refresh your session.<br>You switched accounts on another tab or window. Reload to refresh your session.
Dismiss alert
{{ message }}
AbidiHichem-TunisianCoder
branchless-cardinal-direction-movement
Public
Notifications<br>You must be signed in to change notification settings
Fork
Star
FilesExpand file tree
main
/README.md
Copy path
Blame<br>More file actions
Blame<br>More file actions
Latest commit
History<br>History<br>History
119 lines (83 loc) · 2.94 KB
main
/README.md
Top
File metadata and controls<br>Preview
Code
Blame
119 lines (83 loc) · 2.94 KB
Raw<br>Copy raw file<br>Download raw file
OutlineEdit and raw actions
Branchless Cardinal Direction Movement — A Zero-Dependency Formula
Author: AbidiHichem-TunisianCoder
License: CC BY 4.0
Origin: Tunisia, 2025
The Formula
Δx = 1 - abs(1 - d)<br>Δy = abs(2 - d) - 1
Where d ∈ {0, 1, 2, 3} encodes the four cardinal directions.
Verification
Δx<br>Δy<br>Direction
+1<br>Up
+1<br>Right
-1<br>Down
-1<br>Left
Why This Matters
The universal standard solution uses lookup arrays:
int dx[] = {0, 1, 0, -1};<br>int dy[] = {1, 0, -1, 0};
This formula eliminates that entirely.
Properties:
Zero memory footprint
Zero dependencies — no headers, no arrays, no constants
Branchless when abs is branchless
Works identically in C, C++, Java, Python, GLSL, HLSL,<br>Metal, assembly, any language with abs
No integer size assumptions, no two's complement dependency
Works on 8-bit microcontrollers, GPUs, CPUs, any architecture
This is the minimal possible solution — you cannot encode<br>four cardinal directions with less.
How It Works
Both components sample a phase-shifted triangle wave :
abs(1-d) produces 1, 0, 1, 2 — a V-shape centered at d=1
1 - abs(1-d) shifts it to 0, +1, 0, -1 ✓
abs(2-d) produces 2, 1, 0, 1 — a V-shape centered at d=2
abs(2-d) - 1 shifts it to +1, 0, -1, 0 ✓
The two components are the same arithmetic pattern applied<br>with different phase centers (1 and 2). This is not coincidence<br>— it is the underlying symmetry of the cardinal directions.
GLSL Usage
for (int d = 0; d 4; d++) {<br>int nx = x + (1 - abs(1 - d));<br>int ny = y + (abs(2 - d) - 1);<br>// sample neighbor at nx, ny
No array declarations. No memory access.<br>Pure ALU computation across all parallel threads.
Origin
This formula was discovered in 2025 while coding a Pacman<br>pathfinding implementation in Scratch.
The constraint was personal: a refusal to use branching code<br>and no knowledge of lookup arrays. This forced a search for<br>a purely arithmetic solution.
The Δx component emerged first. The Δy component required<br>pushing past the obvious — nearly giving up — before the<br>constant 2 revealed the symmetry that completes the formula.
Web searches, Bit Twiddling Hacks, HAKMEM, Stack Overflow,<br>and AI language models all return lookup arrays as the<br>standard solution. This formula has no known prior publication.
Applications
Cellular automata on GPU (Conway's Game of Life, etc.)
Grid pathfinding (A*, BFS, Dijkstra)
Tile-based games (Pacman, roguelikes, Sokoban)
Flood fill (image editors, terrain generation)
Robotics and embedded navigation
Image processing (convolution kernels)
Wave Function Collapse procedural generation
Any grid-based simulation
© 2026 AbidiHichem-TunisianCoder. Licensed under CC BY 4.0 — https://creativecommons.org/licenses/by/4.0/
You can’t perform that action at this time.