Author Topic: Fast Langton's Ant (ASM)  (Read 2907 times)

0 Members and 1 Guest are viewing this topic.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Fast Langton's Ant (ASM)
« on: January 20, 2013, 03:44:45 pm »
I was doing laundry again, today, and I thought of a neat way to go about making Langton's Ant in assembly. To give an idea of the speed it runs at, it gets through 10000 iterations in about a second, while updating the screen at each iteration (at 6MHz). This means that you can simulate over 1000000 iterations in under two minutes, on a TI-83+ !

I am sure there are optimisations that can be made, since I threw it together in about an hour and spent another hour tweaking things.

Specifics:
-It uses the whole screen, which is treated as a toroidal (not sure if that is the right word). Basically, if the ant goes of the left edge of the screen, it wraps around to the right.
-Press clear to exit
-It uses whatever contents are on the graph screen as the starting board.
-It only updates one byte at a time in the LCD, that is how it can update so fast.

I might be able to add a way to make it stop after a certain number of iterations, too, if that would be useful. I am just trying to think of a very efficient way of doing that using a 48-bit value for an input x.x Hmm, I might need to use daa for this one >.>

EDIT: For comparison purposes, I downloaded another Langton's Ant program (which is 30 bytes smaller). The screenie is attached. I downloaded another version, but since that used 3 ants, I didn't think it was an accurate comparison. Plus, it used MirageOS and was 62 bytes larger.

Offline pimathbrainiac

  • Occasionally I make projects
  • Members
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1731
  • Rating: +136/-23
  • dagaem
    • View Profile
Re: Fast Langton's Ant (ASM)
« Reply #1 on: January 20, 2013, 06:11:30 pm »
I tried making one of these in AXE... so. slow. by. comparison.

Good Work Xeda!
I am Bach.

Offline tr1p1ea

  • LV7 Elite (Next: 700)
  • *******
  • Posts: 647
  • Rating: +110/-0
    • View Profile
Re: Fast Langton's Ant (ASM)
« Reply #2 on: January 20, 2013, 07:07:26 pm »
Looks to be a very fast and compact implementation, great work as usual Xeda :).
"My world is Black & White. But if I blink fast enough, I see it in Grayscale."


Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Fast Langton's Ant (ASM)
« Reply #3 on: January 21, 2013, 06:21:24 am »
@pimathbraniac: Bug Runer112 to add in a DispGraphPxl-Change( command and that should bring it close to this speed :D
@tr1p1ea: Thanks! I am thinking that there can be more optimisations and since I am not using shadow registers, I might be able to implement a few more things. For example, multiple Ants and inputting a limit on the number of iterations to perform.

EDIT:
First, Runer112 made an awesome optimisation idea on IRC that I want to try at some point. It will bloat the code a little more, but I am looking to speed things up without regard for memory needs. At the moment, it takes 305 bytes on calc, which is nice and small.

Second, you can now have anywhere from 1 to 128 ants on the screen! Unfortunately, this new version works at half the speed, but it is still pretty fast. Unfortunately, I had to make this version in hex (at the moment), so the source isn't presentable. When ORG comes back online, I will try to make sure the assembly source matches the hex and release it.

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: Fast Langton's Ant (ASM)
« Reply #4 on: January 21, 2013, 11:27:33 am »
Just release the hex, it'll be a great exercise for me to traduce it to ASM without any reference ;D

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Fast Langton's Ant (ASM)
« Reply #5 on: January 21, 2013, 11:29:28 am »
I used ASMComp (the program, not the command) so that I didn't have to compute addresses, just to let you know. The attached program is the source that I used.

Offline Spyro543

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1189
  • Rating: +74/-3
    • View Profile
Re: Fast Langton's Ant (ASM)
« Reply #6 on: January 22, 2013, 10:41:30 am »
Yay Vants! I love playing around with them! Do you already have anti-Vants? If not, they should be added.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Fast Langton's Ant (ASM)
« Reply #7 on: January 22, 2013, 12:45:33 pm »
What are those? o.o