How do spaceship search programs work?

For scripts to aid with computation or simulation in cellular automata.
Post Reply
LivingJimbo
Posts: 1
Joined: July 21st, 2020, 6:48 am

How do spaceship search programs work?

Post by LivingJimbo » July 21st, 2020, 7:06 am

I'm fairly new to cellular automatons, but I've recently sparked an interest in them. I've found the spaceships to be really cool, and have come upon spaceship search programs. I've looked through the source code of qfind but was unable to understand the underlying algorithms. Sorry if this is a noob question, but I would appreciate it if someone could explain how it works to me! :)

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: How do spaceship search programs work?

Post by dvgrn » July 21st, 2020, 7:20 am

LivingJimbo wrote:
July 21st, 2020, 7:06 am
I'm fairly new to cellular automatons, but I've recently sparked an interest in them. I've found the spaceships to be really cool, and have come upon spaceship search programs. I've looked through the source code of qfind but was unable to understand the underlying algorithms. Sorry if this is a noob question, but I would appreciate it if someone could explain how it works to me! :)
This post by wildmyron might be a good place to start. BFS = breadth-first search and DFS = depth-first search, and other basic terms used in that message, are not specific to CA or to spaceship search problems, so you can read up about them starting from a standard Google search.

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: How do spaceship search programs work?

Post by Sokwe » July 21st, 2020, 4:17 pm

LivingJimbo wrote:
July 21st, 2020, 7:06 am
I've looked through the source code of qfind but was unable to understand the underlying algorithms.
qfind's algorithm is just gfind but the de Bruijn graphs are replaced by a large lookup table. gfind's algorithm is described in this paper by David Eppstein.

zfind may be easier to understand than qfind or gfind. It works essentially the same way as qfind, but is completely depth-first (rather than breadth-first with depth-first look ahead). You may learn something from browsing the zfind discussion thread.
-Matthias Merzenich

Post Reply