ioribranford

[ioribranford]

TWIL: Theta* pathfinding

This week I learned Theta* pathfinding algorithms for all-angle movement through square grids. These evolved from the classic A*, which builds a path in the form of one-way links from square to square.

A* grid paths are limited to orthogonal and/or diagonal lines depending on the game. This is fine if the environment is mostly tight corridors along those lines, or the actor has fixed goals arranged along those lines. But with dynamic and arbitrary goals in open spaces the path can awkwardly alternate between the lines.

Theta* addresses that problem. It allows walking straight from any square to any other square if there is an unblocked line of sight. Lazy Theta* is an optimized variant that assumes line of sight first and corrects it later.

Review of A*

Keep the following information for each square:

Passable: Depends on the game. At its simplest, the whole square is either Passable or Impassable.

Previous: Which square would be the previous one in the path.

Cost: Cost to reach this square from Start. Equals cost of its previous + distance to its previous. If square is passable but harmful or otherwise not desirable, factor that in too.

Estimated Path Cost (EPC): square’s cost + distance to Goal.

Been Queued: one of three states - No, In Queue, or Yes.

Procedure:

1. Have a priority Queue that sorts squares by increasing (cost + distance to Goal). 2. Put Start in Queue and set its cost to 0. 3. Until Queue is empty, take the next Square off Queue and: 3.1. If Square is the Goal, follow links from Goal back to Start to build the Path and return it. 3.2. If not, go through its Neighbors that have never been in Queue: 3.2.1. Calculate Neighbor’s cost from Square. 3.2.2. If it is Neighbor’s best cost so far: 3.2.2.1. Set it as Neighbor’s cost. 3.2.2.2. Link Neighbor to Square. 3.2.2.3. Add Neighbor to Queue or update its position in Queue.

Converting from A* to Theta*

This can be fine if your grid is not too big.

Before 3.2.1: Check line of sight from Neighbor to Square’s linked square. If not blocked, continue processing the Neighbor against Square’s linked square, not Square itself.

Converting from A* to Lazy Theta*

In 3.2: Process each Neighbor against Square’s linked square, not Square itself.

Before 3.1: Check line of sight from Square to its linked square. If blocked, link Square to its lowest-cost neighbor that has been in Queue, and recalculate Square’s cost from that neighbor.

Line of Sight

The classic line-on-grid algorithm is Bresenham. Note this implementation is meant for undirected lines. It requires modification if you need it to start at a specific point.

If you want a fatter line of sight to avoid squeezing between diagonal blocks, you might try a second and even third line of sight offset by one square, or consider adapting Wu’s anti-aliased line algorithm.

Extra: Approach an Unreachable Goal

Keep track of a Best Goal, that is the closest known square to the Goal. This should be combined with a limit on the number of squares searched, or you will end up searching every reachable square.

Before 3: Set the Best Goal to Start.

After 3.1: If Square is a better goal than Best Goal, set Best Goal to Square.

After 3: Build the Path as in 3.1 but start at Best Goal instead of Goal.

Sources

Wikipedia Theta*

Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D

github.com/zehuilu/Lazy-Theta-with-optimization-any-angle-pathfinding

[ioribranford]

KanaRuru

Stream: https://www.twitch.tv/videos/439304757

[ioribranford]

Some mosCATo for @hentaiphd 's birthday (yesterday)

[ioribranford]

Demonizer prologue storyboard. Reads from right to left.

No time to get it in-game properly (with vfx, sfx, etc) so most likely going to be a free promotional comic.

3/24 Added cover and dialogue

3/26 Added scenes with sister, friend, gameplay

[ioribranford]

Devil Engine is available NOW globally on Switch and Steam!

https://store.steampowered.com/app/891790/Devil_Engine/ https://ec.nintendo.com/JP/ja/titles/70010000017126 https://www.nintendo.com/games/detail/devil-engine-switch

[ioribranford]

Humanoid Tora-neesan

[ioribranford]

Humanoid Haru, looking kind of Maj. Kusanagi-ish.

(I’m reminded of the older cat show that did have Atsuko Tanaka as a cat. It was…OK I guess.)

(No one saw the earlier version with the missing collar and the funny head and the shitty background color right?)

[ioribranford]

Global Game Jam birdy game

With CJ, Karen, David KAAAAAAHHNN, and Dana

[ioribranford]

The second piece of Discord bullet hell winner art!  The request was Royal Arcanist with cat ears and tail.  Nyaa~!

Thanks to all that came into the stream, and to those in the discord who participated!

If you want to play Discord Bullet Hell and suggest art for the game’s art gallery, I’ll be starting another round soon: https://discord.gg/ACTBf2B

[ioribranford]

Today on Nice Idea, Dodgy Execution.

Sleep before you art, kids. Don’t want to run out of steam before you get to polishing.

[ioribranford]

Noh Thank You

Noh Specter beaten by Terri a.k.a. Ellinor in M.U.S.H.A. a.k.a. Musha Aleste.

(with bonus long hair version just for fun)

[ioribranford]

Finally got around to making some actual cover art for this thing!

[ioribranford]

HNY, Pacific.