kikito [Lexaloffle Blog Feed]

locus.p8 - A sparse spatial grid for Pico-8

Sat, 12 Apr 2025 16:21:23 UTC

Locus is a Two-dimensional, unbounded, sparse, efficient, grid spatial hash for Pico-8.

test_locus

by kikito

[Click to Play]

The library uses a grid of squared cells and keeps track of which objects "touch" each cell.

This is useful in several scenarios:

It can tell "Which objects are in a given rectangular section" quite efficiently
This is useful for collision detection; instead of checking n-to-n interactions, locus can be used to restrict the amount of objects to be checked, sometimes dramatically reducing the number of checks.
Given that the query area is rectangular, locus can be used to optimize the draw stage, by "only rendering objects that intersect with the screen"

More Info about the API, FAQ and so on @ github:

https://github.com/kikito/locus.p8

The cart above shows the main features of locus:

Addition and updating of objects in locus
Querying locus for updating objects
Querying locus for drawing objects on the screen

It does not show deletion or filtering, but hopefully the docs on github clarify how to do that.

Feedback most welcome!

oadd - binary insert for pico8

Tue, 18 Feb 2025 21:33:23 UTC

Pico-8 doesn't provide a built-in way to sort arrays.

However it does provide a way to remove items from an array as well as a way to add them to a random position.

A lot of the time a full array-sorting function isn't needed; sometimes it's just enough to be able to insert one item into an already sorted array.

I did look around in the bbs but I didn't find a function for doing it, so here it is:

do
local lt=function(a,b)
 return a<b
end
function oadd(arr,obj,cmp)
 cmp=cmp or lt
 local l,r,m=1,#arr
 while l<=r do
  m=(l+r)\2
  if cmp(arr[m],obj) then
   l=m+1
  else
   r=m-1
  end
 end
 add(arr,obj,l)
 return l
end
end

The function figures out where to insert the item in an already sorted array (using the same algorithm as quicksort) and inserts the new item there.

For arrays of integers or strings it is a drop-in replacement for the built-in add function. The numbers will just be inserted in the right place so that they are sorted. The third optional parameter allows for using different comparation functions. Example:

local by_z=function(a,b) return a.z<b.z end
local obj1={z=14}
local obj2={z=5}
local arr={}
oadd(arr,obj1)
oadd(arr,obj2) -- arr should be {obj2,obj1} since obj2.z is smaller.

Attaching demo cart:

oadd demo

by kikito

[Click to Play]

hit.p8 - continuous collision detection for rects

Sat, 05 Oct 2024 16:25:33 UTC

Hit

Hello Pico-8 community!

Rectangles ("Axis-Aligned Bounding Boxes", or aabbs, or simply boxes) are the most common way to detect collisions in videogames. Checking that two rectangles intersect is easy and fast.

However sometimes game objects need to move fast. Projectiles or even hedgehogs sometimes move so fast that they traverse many pixels per frame. When they move fast enough they can "phase through" objects, if one uses simple rectangle intersection as a mean to detect collisions.

Even when the two rectangles intersect, it can be tedious/tricky to find exactly on which position do they land.

I present you hit. It's a single function which will solve this particular problem, doing continuous collision detection instead of simple intersection.

hit

by kikito

[Click to Play]

Parameters and return values

tx,ty,nx,ny,t,intersect = hit(x1,y1,w1,h1,x2,y2,w2,h2,goalx,goaly)

Hit takes 10 parameters:

x1,y1,w1,h1: A first rectangle, represented by its top-left coordinate, a width and height
x2,y2,w2,h2: A second rectangle
goalx,goaly: A point in space where the first rectangle "wants to move" (x1,y1 "wants to become" goalx,goaly)

Hit returns nil if the first rectangle can move freely to goalx,goaly without touching the second rectangle. If the rectangles touch at any point during this journey, hit will return:

tx,ty: the coordinates where the first rectangle's top-left corner would be when it starts touching the second rectangle
nx,ny: the "normals" of the contact. Given that we are dealing with aabbs, nx and ny will always be either -1,0 or 1
t: "how far along" the journey did the contact occur. 0 means that the two boxes touch right at the beginning of the journey, and 1 means they touch at the end. In some degenerate cases t can also be bigger than 1 or smaller than 0 (see below). This parameter is useful for sorting collisions (the one with the smaller t will usually have "happened" first)
intersect: true if the boxes were intersecting at the beginning of the journey, false if they were not. This parameter is useful to treat intersections differently from non-intersections in the collision resolution

Usage

Save the hit function to a single file (hit.lua) and then

#include hit.lua

Cost

Hit costs 422 tokens approximately. Most of the tokens come from the calculation of tx,ty,nx and ny. If those are not needed, then it can be strip down to a much leaner function that only returns true or false.

The function has several comments which can be stripped in order to save characters if necessary.

Performance-wise, it is not very expensive. There will be always some calls to abs, and number comparisons. For non-degenerate cases there will always be 4 divisions per collision detection.

Notes and degenerate cases

When dealing with collision detection, there's many edge cases to take into account. Some of them are not obvious:

No displacement vector: x1,y1 is equal to goalx,goaly already. In this case, hit will return nil if the aabbs don't intersect. If they do intersect, however, then hit will return "the shortest path that would move the first aabb out of the second aabb". This can be either up, down, left or right, depending on what the nearest path is.
First aabb is already intersecting the second aabb at the beginning of the journey. In this case hit will also try to move it towards the shortest exit, but in the direction of the displacement. Note however this can also send the object backwards in the direction it wants to go, if that's the sortest path out. Also note that when the objects are intersecting it is possible that t is either smaller than 0 or bigger than 1
Corners: hit does not make any guarantees about collisions being detected if they happen to touch in a single point (e.g. the journey would make two corners coincide) or in a single line (the first aabb moves in such a way that it "slides" over the second, without trying to intersect it). On this cases it may or may not report a collision.
Precision: given Pico-8's limited floating point representation, the coordinates tx and ty will often not coincide precisely with what would result by multiplying the displacement vector (goalx-x1,goaly-y1) by t. Hit will "hide" this problem by moving things slightly in order to make the touch "feel" correct despite that, as much as the floating point representation permits.

Preemptive FAQ

How does hit work?

Hit combines two algorithms: The Minkowsky Difference and the Liang-Barsky line clipping algorithm.

The Minkowsky difference is a geometrical operation, where one object "gets smoothed over" the perimeter of another object. If you do the minkowsky difference between a square and a circle you will get a bigger square with rounded corners. When you do the minkowsky difference between two aabbs you get another (bigger) aabb.

The neat thing about this is that if you make one of the rectangles "bigger", you can make the other "smaller", and the properties of the collision work the same (as long as you respect some norms). If we make one of the rectangles as big as the Minkowsky diff, we can make the other one as small as a single point.

Which means that our "how do I collide these two moving boxes with each other" gets simplified to "how do I intersect this bigger box with this pixel that is moving, in other words, this segment".

The family of algorithms that solve this particular problem is called "line-clipping algorithms", and the Liang-Barsky one seems to be the fastest generic one. So we clip the diff with the segment, which gives us t and the normals. We then calculate tx and ty, paving over the floating point imprecision as much as possible.

Why no guarantees on the corner cases?

I have done this kind of thing before, and it is simply too time consuming for me. I would rather stop here.

Where have you done this kind of thing before?

I am the original author of the bump.lua library, used for collision detection in Lua/LÖVE , which is somewhat popular. There's some things I learned while writing that library, that I have tried to avoid/simplify while doing this Pico8 version.

Bump.lua had collision resolution. Why doesn't hit have that?

Bump.lua is also much bigger, and includes a whole spacial hash implementation as well.

Have you used this on an actual videogame?

I am building one, this is but one of the pieces.

I found a bug, can I contribute

Yes. https://github.com/kikito/hit.p8

It can take me a while to answer. Sorry!

ins - inspect for PICO-8

Sun, 17 Oct 2021 23:37:48 UTC

Here's a function that will transform whatever you pass it into a table that will hopefully be understandable by a human. It'll take any table or other Lua value, so you can, for example, print it:

print(ins({1,2,3,foo=bar}),1,1)
printh(ins({1,2,3,foo=bar}))

The only parameter besides the string to be transformed is the depth.

local deep={l1={l2={l3={l4="!"}}}}}
print(ins(deep)) --prints everything
print(ins(deep,2)) --stops at l2 and prints {_}

ins:inspect for PICO-8

by kikito

[Click to Play]

As the author of the inspect.lua library, I use it a lot on my day job when I need to debug Lua, and I really miss it when debugging in Pico-8. I found some previous efforts on this direction, but I was missing a lot:

Marking repeated tables, functions, threads and userdata with numbers
Handling nested tables / avoiding printing repeated tables
Sorting keys sensibly
Printing metatable data
Presenting arrays as comma-separated single lines, and hashes in multiple-span lines

I made ins' output take less horizontal space than inspect.lua, so it adapts better to PICO-8's output. And I trimmed features(string escaping, preprocessing).

Still, at ~700 tokens, it's ... a chunky boy. You probably shouldn't add it to your project permanently. Think of it as a "debug artillery" function: deploy it to a tab in your game, it should be able to handle whatever you throw at it and return a digestible string. Once you have used it to destroy your problem, remove it.

PS: My biggest surprise was that PICO-8 has no built-in sorting function. So I bundled one. Oh and there is no concat, either. The garbage collector must be having fun with all those strings :)

EDIT: fixed bug in isidentifier function

A Convenient Generalization of Schlick's Bias and Gain Functions

Thu, 22 Oct 2020 08:54:49 UTC

This is an implementation of the function described on this short paper:

https://arxiv.org/abs/2010.09714 (twitter thread)

It is amenable to tweeing/easing in games. I have programmed easing functions in the past and one of the problems about them is that you need to code "families of easing functions":

(That's from tween.lua, if you are curious).

I like this function because it can aproximate all of the "smooth families of functions" on that graph (all except the "back", "bounce" and "elastic" families) with a single function, plus it adds an infinitude of variants. Not bad for ~66 tokens.

schlick_bias_gain

by kikito

[Click to Play]

Usage:

y = easing(x,t,c)

All params (x, t and c) are restricted to the [0,1] interval. When they are, the result (y) is also in the [0,1] interval.

x is the input being eased. In games and animations this usually encodes "the percentage of time that has passed since the start of the animation". Notice that x is restricted to [0,1]. If the magnitude you are trying to ease is not on that range, you might have to scale it (like I did in order to display the graphs).
t is "the threshold point" - that's the location of the "inflection" in the curve (the point at which the curve switches from out to in, or viceversa).
c is "the curvature". At 0-0.5 the curve will "start in in", gradually approaching linear interpolation at 0.5, and then the curve will "start in out" the more it approaches 1 from there.
y is the return of the easing. In games and animations this is often the "percentage of space the thing moves, for the time that has passed". Like with x, it will be on the [0,1] range, so it might need scaling.

Usually x changes over time, while t and c are "fixed" during an animation. On the attached Cartridge they are animated, but only because we show the whole curve.

There are a couple differences between my implementation and the one in the paper:

I had to add 1 to the x>=t branch of the function. I believe this is because Pico-8's y-axis goes "down" instead of up, like in "regular math". Not 100% sure about this.
The s parameter described in the paper is a "slope". When it goes from 0 to 1 it acts "one way", making the curve more "steep" at the beginning and when it goes from 1 to infinity it acts "the other way", making it more steep at the end. I replaced s with c (c = 1/(s+1)), so that it stays on the [0,1] range, like the other params.

Giraffe-Eating Leaves

Thu, 06 Aug 2020 23:54:00 UTC

This is a simple game I made with my (now 4-year-old) son. Perhaps influenced by Lexaloffle's BBS icon, its protagonist is a giraffe. It eats falling leaves.

giraffeeatingleaves

by kikito

[Click to Play]

It has no victory or defeat conditions (my son still doesn't demand them, so I keep not including those).

I wanted my son to start getting used to a mouse, so this game has mouse support! It was fun having to activate it via POKEs. (I was reminded of the Sinclair Spectrum 48k of my youth). The game also works with the default "button-based" control scheme.

Arrows: Move head
X: Eat

The code, as usual, has been heavily cleaned up before posting.

Notes about the graphical design:

I only programmed the giraffe head and the leaves with my son. The telescopic neck and body at the bottom was added as a surprise, later on.
On that note, I am very aware that giraffe's mouths are on their snouts, not on their necks. If you feel the need to comment about this particular anatomical anomaly, let me point out that this particular giraffe has a telescopic neck and its legs don't move while it walks.
The pinkish falling ... "things" are supposed to be leaves. I think they look more like beets, but my 4yo Chief of Design was very adamant about the colors and shape.

Car Coins Corona

Thu, 02 Jul 2020 23:45:21 UTC

This is the second game my 3-years-old son and I did together.

It started as something simple. A car which moves around. A police car? No, a regular car.

Then we added coins. And made the car pick them! Interactivity! Randomness!

Then we needed a monster. So of course Covid-19 makes an appearance as the bad guy. You "kill it" with the car (which conveniently uses the same code as the coins).

Although to more experienced players the game might feel like it needs some kind of "success screen", my son doesn't seem to miss it at all.

It was also the first time we used the sound editor. Bruno is way too impatient, and I am too inexperienced, to create a whole song for a game just yet.

Fun facts:

There's exactly 10 instances of the virus because that's the biggest number Bruno is able to count up to so far (reliably).
There's exactly 51 coins because "51" is the number Bruno uses when he wants "a very big number".

Controls: arrows to move.

carcoinscovid

by kikito

[Click to Play]

I was not yet familiar with pico-8's add, del, and foreach so the first version of this had a lot of duplicated code and it was a bit of a mess (try coding next to a 3-year old child to see what I mean!). I cleaned it up before posting.

Dino watering flowers

Tue, 23 Jun 2020 20:49:55 UTC

Today was the first day I did a videogame with my son.

He's 3 years old. He helped me pick all the colors and with design decision, like what kind of dinosaur to include and what he would be doing.

The game itself is literally 6 if blocks, and I wrote it pretty quickly, starting from api.pb . It still felt like an eternity to my toddler! He could see progress while I was drawing the dino and the flowers, but the programming part was meaningless to him. He was vociferously demanding progress. A true client. I had to cut many features. Bounds checking, for example, only works partially. It became a feature ("ooooh where did the dinosaur go?")

CONTROLS: Move with arrows, water flowers with Z.

Cleaned up before publishing.

dinowateringflowers

by kikito

[Click to Play]