Log In  
Follow
samhocevar
Follow

Here is a simple implementation of merge sort in 97 tokens. It uses less PICO-8 CPU than anything else I’ve tried (with a caveat, see below).

A small benchmark comparing CPU usage, sorting an array of 200 random numbers:

Note that non-randomised quicksort suffers from very bad performance on quasi sorted lists, so the above benchmark does not represent what you would get in real life. Always test in your own application.

function sort(t, a, b)
    local a, b = a or 1, b or #t
    if (a >= b) return
    local m = (a + b) \ 2
    local j, k = a, m + 1
    sort(t, a, m)
    sort(t, k, b)
    local v = { unpack(t) }
    for i = a, b do
        if (k > b or j <= m and v[j] <= v[k]) t[i] = v[j] j += 1 else t[i] = v[k] k += 1
    end
end

In real life merge sort performs worse than e.g. quicksort because it suffers from poor locality of reference (cache misses), but in a high level language such as Lua this becomes meaningless.

To any computer scientist this specific implementation would be badly written and would appear to perform extremely poorly because {unpack(t)} effectively copies the whole array n×log(n) n times. However, in PICO-8 world this function is ridiculously fast because for the virtual CPU the operation is almost free. Use at your own risk because the actual CPU running PICO-8 will still perform the operations!

Another limitation: does not support arrays of more than 16384 elements because of the overflow in (a+b)\2. Just replace with (a/2+b/2)\1 if necessary.

Edit: here is a version that performs log(n) full array copies and is thus much lighter on the CPU. It is also about 10% faster. The drawback is that it’s now 111 tokens, but that’s still pretty good.

function sort(t)
  local function f(a, b)
    if a < b then
      local d = (b - a) \ 2 + 1
      f(a, a + d - 1)
      f(a + d, b)
      local v, j, k = { unpack(t, a, b) }, 1, d + 1
      local vj, vk = v[j], v[k]
      for i = a, b do
        if (not vk or j <= d and vj <= vk) t[i] = vj vj = v[j] j += 1 else t[i] = vk vk = v[k] k += 1
      end
    end
  end
  f(1, #t)
end
P#78990 2020-07-06 16:04 ( Edited 2020-07-07 10:18)

Here are a few token count discrepancies:

print(12)    -- 3 tokens
print(-12)   -- 3 tokens
print(~12)   -- 3 tokens
print(-~12)  -- 4 tokens
print(~-12)  -- 5 tokens
print(~~12)  -- 4 tokens

?12    -- 2 tokens
?-12   -- 3 tokens
?~12   -- 2 tokens
?-~12  -- 3 tokens
?~-12  -- 4 tokens
?~~12  -- 3 tokens

Also this inconsistent behaviour with spaces:

print(-12)   -- 3 tokens
print(- 12)  -- 4 tokens
print(~12)   -- 3 tokens
print(~ 12)  -- 3 tokens
P#77843 2020-06-09 10:18 ( Edited 2020-06-09 10:36)

I recently wrote a post about storing random data as strings in carts and studying the built-in compression algorithm. It led, among other conclusions, to the following two observations:

  • PICO-8 is not very good at compressing random strings that use more than 64 different characters; those get actually expanded by about log₂(n)/6. For instance a random string of length 1000 that uses 128 different characters will use 1000*log₂(128)/6 = 1167 bytes in the cart.
  • The new compression format is redundant and allows for sequences that are not needed. For instance 011 01111 001 and 010 0000001111 001 both encode a back reference of length 4 at offset -16.

Most other compression schemes have some sort of fallback mechanism when they are unable to compress a block. For instance the DEFLATE format (for zip or gzip) has non-compressed blocks. In the above thread I made a suggestion to extend the compression format in a similar way, but here I have a much simpler proposal:

  • 010 00000 marks the start of a zero-terminated sequence of uncompressed bytes

This works because:

  • 010 00000 never happens in a compressed stream; anything that would start with that sequence could start with 011 instead and be much shorter
  • the null byte is not allowed in the code
  • the overhead is only two bytes; it can be more efficient than the current format for some strings as short as 7 characters
  • it should be easy to adapt the existing compressor so that when it realises the last X bytes have compressed badly it backtracks and stores the bytes instead
P#77839 2020-06-09 09:33

I would like to propose the following syntax extensions to PICO-8 for symmetry with the shorthand peek operators. Basically it means treating the peek operators result as an lvalue:

@x = y     -- short for poke(x,y)
%x = y     -- short for poke2(x,y)
$x = y     -- short for poke4(x,y)

@x += z       -- short for poke(x, @x + z)
%12 |= %42    -- short for poke2(12, %12 | %42)
$x >><= 4     -- short for poke4(x, $x >>< 4)
P#77838 2020-06-09 08:41

The following operators cost 2 tokens instead of the usual 1 for compound assignment operators:

\=
^=
>><=
<<>=
..=

edit: I confused >>>= and ^= in my initial post.

P#77804 2020-06-08 17:43 ( Edited 2020-06-08 22:07)

I’m writing a minifier and I still can’t really wrap my head around the parser.

Here are two similar snippets that differ only in whitespace and do not do the same thing:

> for i=1,2 do
>  if(i)print(i) end
> print(3)
1
2
3
> for i=1,2 do
>  if(i)print(i) end print(3)
1
3
2
3
P#77774 2020-06-07 22:07

When attempting to load a .p8 cart that exceeds the 65535 character limit (one that may have been created by an external editor or tool), PICO-8 silently drops lines at the end of the cart and does not report errors. It then accepts to save the (now corrupted) cart when pressing Ctrl-S, overwriting the original file.

Here is a sample cartridge for testing purposes; notice that the last print() line disappears when loading it.

One more observation: sometimes, when the 65535 character threshold lies in the middle of a Lua statement, a loading error does appear. I have been unable to identify when exactly.

P#77260 2020-05-27 08:54

I created a cart containing the following code:

print("hello")

Then in the shell:

save foobar.p8.png

If I close PICO-8 and reopen foobar.p8.png, I get gibberish in the code section:

P#77228 2020-05-26 17:09

Due to the preprocessor parsing numbers differently than Lua, here are some issues:

Valid code (1e-3 is a valid number in Lua):

a=1e-3

Invalid code (1e-3 is parsed as 1 e - 3 by the preprocessor):

a+=1e-3

Invalid code (2b is an invalid number in Lua):

a=1+2b=3

Valid code (2b is parsed as 2 b by the preprocessor):

a+=1+2b=3
P#76926 2020-05-19 21:47

Not sure if it is really a bug, but poking at the 8 bytes starting at 0x5f4c then immediately peeking will discard the two highest bits:

> p=0x5f4c poke(p,255) print(@p)
63

I know this is a special area and the memory is modified by the virtual hardware between frames, but no other location discards bits like that.

P#76883 2020-05-19 08:55

The new shift operator behaviour where a>>n returns a<<-n when n is negative causes an infinite loop and freezes PICO-8 when shifting by -32768:

?1<<-32768
?1>>-32768
?1>>>-32768
P#75893 2020-05-05 21:52

shr(x,n) and lshr(x,n) have always handled shift values outside the 0…31 range in a peculiar way: negative values of n are treated like n&31, while values ≥ 32 always return 0 (or 0xffff.ffff for a signed shift).

But now the new >>> operator diverges from lshr by treating n ≥ 32 like n&31, so we get:

   1 >> 32 = 0
 shr(1,32) = 0
  1 >>> 32 = 1
lshr(1,32) = 0

edit: same with << which no longer behaves like shl()

P#75744 2020-05-02 13:43 ( Edited 2020-05-02 13:47)

Just a few things I thought I’d share. Sorry if it’s gibberish and/or uninteresting to most people.

Many carts store extra data in the code section, most of the time inside strings. Some people will store structured data such as JSON or JSON-like data and let the PICO-8 compression mechanism deal with it, but you must have seen people who rolled their own compression mechanism and use custom formats such as modified base64 that takes advantage of the 59 “good” characters (i.e. the ones that needed only one byte of storage in the .p8.png format instead of two).

-- custom base64 data
local data = "e*!jfg57yfl+[7dmrin_bt#0/g6!1y68(.xh.ata_kn3j7!un_s+jn5..a)s8xi/ou0/{ff)ec}["

Such base64 data encodes 6 bits of information per character, and requires an average of 8.625 bits per character on the old format cartridge (pre-0.2.0). It means that this “alphabet” gave us about 5.565 bits of information per byte on the cartridge (8 * 6 / 8.625).

The new compression format is now charset-agnostic; there is no reason to use custom encodings and favour those 59 characters. We can therefore use standard base64 as far as only storage is concerned (when thinking about decoder complexity, using a contiguous alphabet would be smart):

-- base64
local data = "RpUpAUT80Jf6CQakfKLHz+1BSpUxFUYa/JDtdeAo4cyC1tHDx6gpazu0kdJqFdX+e4rMvfA+Ua0L"

This data still encodes 6 bits of information per character, but now requires an average of 8 bits per character on the new format cartridge, giving us exactly 6 bits of information per byte on the cartridge (better than the old compression method).

So I wondered: what about other alphabets? (of more or less than 64 characters)

Here are the theoretical results, assuming perfectly random data and ignoring the fact that the compression algorithm may emit back references:

Here are my conclusions:

  • the new compression algorithm always outperforms the old one for random data
  • starting from about 40, alphabet size no longer really matters (there are “peaks” around 48 and 112 but probably not worth exploiting)

In a future post I will study the effect of the back reference emission (which are rare on random data but non-negligible with small alphabet sizes), but I’ll wait for 0.2.0e to be out since Zep mentioned on Twitter that he fixed something in the compression.

P#75683 2020-05-01 07:03

Not really a bug, but I accidentally discovered that '!' now gets replaced with 'self' at runtime, except when followed by '=':

> !ish = 42
> ?selfish
42

This is a bit confusing because in other languages, ! is an operator, whereas here it behaves almost like any other letter.

P#75065 2020-04-20 21:34

I made a tiny plugin that lets Tiled load .p8 cartridges, edit the map section, and save them back without breaking the code or other sections. Works great for me, so I hope you may find it interesting!

Available on GitHub: https://github.com/samhocevar/tiled-pico8

Here is what it looks like with a dark theme and the grid color set to white:

P#74934 2020-04-18 16:44

On Windows, when launching a cart that uses #include, all included files get locked forever and cannot be deleted or modified by an external program unless PICO-8 is stopped. Even if another cart is loaded, the old files are still locked. This makes it really hard to work with source control because no file can be updated or merged while PICO-8 is running.

Edit: here is a screenshot of resmon.exe showing that pico8.exe acquires a new file descriptor on the same file each time I press Ctrl-R:

P#74928 2020-04-18 12:12 ( Edited 2020-04-18 18:20)

Operator >>>= is mentioned in the 0.2 changelog, but the parser does not seem to recognise it:

x >>>= y
syntax error near '>'

Apparently the preprocessor changes the code to:

x > = > >> ( y)
P#74808 2020-04-16 07:37

In the command prompt, this will work (where ⎵ denotes a space):

  • load⎵#15133
  • load⎵"#15133"
  • load("#15133")
  • ⎵load("#15133")
  • ⎵load⎵("#15133")

However this will throw syntax errors:

  • load⎵⎵#15133
  • ⎵load⎵#15133
  • load⎵⎵"#15133"
  • load⎵("#15133")
P#73279 2020-02-20 09:40

I know several people already created TTF fonts, but I believe this goes slightly beyond.

This cart is a tool that vectorises the PICO-8 font and exports it to %APPDATA%/pico-8/carts/font.sfd.p8l . You can then open that file in FontForge and modify it to your will, then export it as TrueType, PostScript etc.

It should be fully forward-compatible and if Zep ever changes a glyph, then the resulting TTF file will change accordingly.

For instance, if you are lucky enough to have a PICO-8 Gold Account™ and the latest preview version with the chr() function and the kana glyphs you’ll even get Japanese support:

Here it is in action in the Windows font settings:

And here it is in a toy application:

Cart #makefont-0 | 2019-12-03 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
4

P#70527 2019-12-03 13:03

Cart #nothing-1 | 2019-10-12 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
10

This is the game @Niarkou and I made for Ludum Dare 45 in 72 hours.

Ludum Dare entry page · GitHub source code

A few warnings about this version:

  • the ball does nothing
  • the cave is not implemented
  • there is no reward for watering the plants
  • there is no reward for the riddle
  • there is a large empty area at the east

We want to work on the game and improve the story when the Ludum Dare voting period is over. Hope you already enjoy it as it is now, though!

P#68785 2019-10-12 10:55 ( Edited 2019-10-12 11:01)

View Older Posts
Follow Lexaloffle:        
Generated 2020-12-04 17:45 | 0.225s | 4194k | Q:92