Skip to content

Instantly share code, notes, and snippets.

@thetarnav

thetarnav/a_star.odin

Last active July 23, 2024 21:29
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save thetarnav/a453488e1d2be44a1a515f8a3e3be3da to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save thetarnav/a453488e1d2be44a1a515f8a3e3be3da to your computer and use it in GitHub Desktop.
Download ZIP
A* Path Finding Algorithm in Odin
Raw
a_star.odin
package game
import "core:slice"
import "../grid"
astar :: proc (
path: ^[dynamic]grid.Coord,
grid_walls: grid.Grid(bool),
init, goal: grid.Coord,
) -> bool {
heuristic :: grid.distance
Pos_With_Cost :: struct {p: grid.Coord, cost: f32}
/*
g cost - cells to move from initial position
f cost - distance to goal position
from - posititon that you came from
*/
grid_g := grid.make(f32 , grid_walls.size, context.temp_allocator)
grid_f := grid.make(f32 , grid_walls.size, context.temp_allocator)
grid_from := grid.make(grid.Coord, grid_walls.size, context.temp_allocator)
grid.fill(&grid_g, -1)
init_f_cost := heuristic(init, goal)
grid.set(&grid_g, init, 0)
grid.set(&grid_f, init, init_f_cost)
open_list := make([dynamic]Pos_With_Cost, 0, grid.len(grid_walls)/2, context.temp_allocator)
append(&open_list, Pos_With_Cost{init, init_f_cost})
for len(open_list) > 0 {
current := pop(&open_list).p // pop one with lowest f cost
if current == goal {
p := current
for p != init {
append(path, p)
p = grid.get(grid_from, p)
}
slice.reverse(path[:])
return true
}
DIRECTIONS :: [?]Pos_With_Cost{
{{-1, 0}, 1},
{{ 1, 0}, 1},
{{ 0, -1}, 1},
{{ 0, 1}, 1},
{{-1, -1}, SQRT_TWO},
{{ 1, 1}, SQRT_TWO},
{{ 1, -1}, SQRT_TWO},
{{-1, 1}, SQRT_TWO},
}
for d in DIRECTIONS {
neighbor := current + d.p
(grid.inside(grid_walls, neighbor) && !grid.get(grid_walls, neighbor)) or_continue
neighbor_g_cost_new := grid.get(grid_g, current) + d.cost
neighbor_g_cost_old := grid.get(grid_g, neighbor)
(neighbor_g_cost_old == -1 || neighbor_g_cost_new < neighbor_g_cost_old) or_continue
neighbor_f_cost := neighbor_g_cost_new + heuristic(neighbor, goal)
grid.set(&grid_from, neighbor, current)
grid.set(&grid_g, neighbor, neighbor_g_cost_new)
grid.set(&grid_f, neighbor, neighbor_f_cost)
insert_ordered_by(&open_list, Pos_With_Cost{neighbor, neighbor_f_cost}, high_to_low_compare)
high_to_low_compare :: proc (a, b: Pos_With_Cost) -> slice.Ordering {
return slice.cmp(b.cost, a.cost)
}
}
}
return false
}
jps :: proc (
path : ^[dynamic]grid.Coord,
grid_walls: grid.Grid(bool),
init, goal: grid.Coord,
) -> bool {
heuristic :: grid.distance
Pos_With_Cost :: struct {p: grid.Coord, cost: f32}
/*
g cost - cells to move from initial position
f cost - distance to goal position
from - posititon that you came from
*/
grid_g := grid.make(f32 , grid_walls.size, context.temp_allocator)
grid_f := grid.make(f32 , grid_walls.size, context.temp_allocator)
grid_from := grid.make(grid.Coord, grid_walls.size, context.temp_allocator)
grid.fill(&grid_g, -1)
init_f_cost := heuristic(init, goal)
grid.set(&grid_g, init, 0)
grid.set(&grid_f, init, init_f_cost)
open_list := make([dynamic]Pos_With_Cost, 0, grid.len(grid_walls)/2, context.temp_allocator)
append(&open_list, Pos_With_Cost{init, init_f_cost})
for len(open_list) > 0 {
current := pop(&open_list).p // pop one with lowest f cost
if current == goal {
/* Reconstruct the path by backtracking */
p := current
for p != init {
append(path, p)
p = grid.get(grid_from, p)
}
slice.reverse(path[:])
return true
}
/*
Jump Point Search
*/
DIRECTIONS :: [8]grid.Coord{
{-1, 0},
{ 1, 0},
{ 0, -1},
{ 0, 1},
{-1, -1},
{ 1, -1},
{-1, 1},
{ 1, 1},
}
for d in DIRECTIONS {
p := jump(grid_walls, current, d, goal).? or_continue
cost_g_old := grid.get(grid_g, p)
cost_g_new := grid.get(grid_g, current) + heuristic(current, p)
if cost_g_old == -1 || cost_g_new < cost_g_old {
cost_f := cost_g_new + heuristic(p, goal)
grid.set(&grid_from, p, current)
grid.set(&grid_g, p, cost_g_new)
grid.set(&grid_f, p, cost_f)
insert_ordered_by(&open_list, Pos_With_Cost{p, cost_f}, high_to_low_compare)
high_to_low_compare :: proc (a, b: Pos_With_Cost) -> slice.Ordering {
return slice.cmp(b.cost, a.cost)
}
}
}
}
jump :: proc (walls: grid.Grid(bool), p, d, goal: grid.Coord) -> Maybe(grid.Coord) {
for p := p+d;; p += d {
if !grid.inside(walls, p) || grid.get(walls, p) {
return nil
}
if p == goal {
return p
}
switch d {
case {-1, -1},
{ 1, -1},
{-1, 1},
{ 1, 1}:
// +---+---+---+
// | ↘ | | |
// +---+---+---+
// | W | P | |
// +---+---+---+
// | E | ↓ | |
// +---+---+---+
if ((grid.inside(walls, {p.x-d.x, p.y+d.y}) &&
grid.get (walls, {p.x-d.x, p.y }) &&
!grid.get (walls, {p.x-d.x, p.y+d.y})) ||
// +---+---+---+
// | ↘ | W | E |
// +---+---+---+
// | | P | → |
// +---+---+---+
// | | | |
// +---+---+---+
((grid.inside(walls, {p.x+d.x, p.y-d.y}) &&
grid.get (walls, {p.x , p.y-d.y}) &&
!grid.get (walls, {p.x+d.x, p.y-d.y})) ||
/* expand vertically */
jump(walls, p, {0, d.y}, goal) != nil) ||
jump(walls, p, {d.x, 0}, goal) != nil)
{
return p
}
case {-1, 0},
{ 1, 0}:
// +---+---+---+
// | | W | E |
// +---+---+---+
// | → | P | → |
// +---+---+---+
// | | W | E |
// +---+---+---+
if /* UP */
(grid.inside(walls, {p.x+d.x, p.y+1}) &&
grid.get (walls, {p.x , p.y+1}) &&
!grid.get (walls, {p.x+d.x, p.y+1})) ||
/* DOWN */
(grid.inside(walls, {p.x+d.x, p.y-1}) &&
grid.get (walls, {p.x , p.y-1}) &&
!grid.get (walls, {p.x+d.x, p.y-1}))
{
return p
}
case { 0, -1},
{ 0, 1}:
// +---+---+---+
// | | ↓ | |
// +---+---+---+
// | W | P | W |
// +---+---+---+
// | E | ↓ | E |
// +---+---+---+
if /* RIGHT */
(grid.inside(walls, {p.x+1, p.y+d.y}) &&
grid.get (walls, {p.x+1, p.y }) &&
!grid.get (walls, {p.x+1, p.y+d.y})) ||
/* LEFT */
(grid.inside(walls, {p.x-1, p.y+d.y}) &&
grid.get (walls, {p.x-1, p.y }) &&
!grid.get (walls, {p.x-1, p.y+d.y}))
{
return p
}
}
}
}
return false
}
Raw
grid.odin
package grid
import "base:builtin"
import "base:runtime"
import slice_pkg "core:slice"
import "core:math/linalg"
import "core:log"
Grid :: struct ($T: typeid) {
data: [^]T,
size: [2]int,
}
Coord :: distinct [2]int
make_empty :: proc (
$T: typeid,
size: [2]int,
allocator := context.allocator,
loc := #caller_location,
) -> (
grid: Grid(T),
error: runtime.Allocator_Error,
) #optional_allocator_error
{
grid.size = size
grid.data = builtin.make([^]T, size.x * size.y, allocator, loc) or_return
return
}
make_from_data :: proc (data: []$T, size: [2]int) -> (grid: Grid(T)) {
assert(builtin.len(data) == size.x * size.y)
grid.size = size
grid.data = raw_data(data)
return
}
make :: proc {make_empty, make_from_data}
delete :: proc (grid: Grid($T)) {
builtin.delete(grid.data[:grid.size.x*grid.size.y])
}
idx :: #force_inline proc "contextless" (grid: Grid($T), p: Coord) -> int {
return x + y * grid.size.x
}
to_x :: #force_inline proc "contextless" (grid: Grid($T), i: int) -> int {
return i % grid.size.x
}
to_y :: #force_inline proc "contextless" (grid: Grid($T), i: int) -> int {
return i / grid.size.x
}
to_xy :: #force_inline proc "contextless" (grid: Grid($T), i: int) -> (p: Coord) {
return {i % grid.size.x, i / grid.size.x}
}
get :: #force_inline proc "contextless" (grid: Grid($T), p: Coord) -> T {
return grid.data[p.x + p.y * grid.size.x]
}
ptr :: #force_inline proc "contextless" (grid: ^Grid($T), p: Coord) -> ^T {
return &grid.data[p.x + p.y * grid.size.x]
}
set :: #force_inline proc "contextless" (grid: ^Grid($T), p: Coord, v: T) {
grid.data[p.x + p.y * grid.size.x] = v
}
set_idx :: #force_inline proc "contextless" (grid: ^Grid($T), i: int, v: T) {
grid.data[i] = v
}
inside :: #force_inline proc "contextless" (grid: Grid($T), p: Coord) -> bool {
return p.x >= 0 && p.x < grid.size.x && p.y >= 0 && p.y < grid.size.y
}
len :: #force_inline proc "contextless" (grid: Grid($T)) -> int {
return grid.size.x*grid.size.y
}
slice :: #force_inline proc "contextless" (grid: ^Grid($T)) -> []T {
return grid.data[:grid.size.x*grid.size.y]
}
zero :: proc (grid: ^Grid($T)) {
slice_pkg.zero(slice(grid))
}
fill :: proc (grid: ^Grid($T), v: T) {
slice_pkg.fill(slice(grid), v)
}
distance :: proc (a, b: Coord) -> f32 {
return linalg.distance([2]f32{f32(a.x), f32(a.y)}, [2]f32{f32(b.x), f32(b.y)})
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment