0
\$\begingroup\$

I'm trying to create a snake game on a Xilinx Artix7 FPGA, and one of the things I want to check is if the snake has collided with itself. I need to perform this check between game updates to know by the next update whether the game has ended.

The snake in my game is made up of discrete segments, so to check if the snake has collided with itself, I just check if the first segment (the head) overlaps with either the second, the third, the fourth, etc. My plan is to do this sequentially with a clock much faster than the game clock.

The thing is I think I can get away with only checking if the head collides with every other segment. However, is there really any advantage gained by this "optimization"?

The game, if running at say 50 FPS, would have an update period 20 ms. The clock the Basys3 board supports is 100 Mhz which is a period of 10 ns. This means that in the interval between updates for the game, I can go through 2 million segments, which is far more than the snake could ever have. Since the game doesn't really need to get faster than 50 FPS, finding the answer twice as fast doesn't do anything because all I would do is just sit around and wait for the next update.

Another thing I thought of was maybe I could configure the create_clock command in my XDC (constraints) file to be slower, but is there an advantage to doing so? Does it consume less power or something?

The last thing I could think of is if I used a combinational version of collision checking like so

(head == seg1) || (head == seg 2) || (head == seg3) || ... || (head == segN)

With my optimization, it would only take half as much hardware, but still way more than the sequential version. Since it's combinational, the answer would be available almost instantly, but again, since I've got time to kill, I don't see an advantage there either.

Is this a useless optimization?

\$\endgroup\$
0
\$\begingroup\$

How is this chip supposed to make the snake visible? The normal approach would be to render the snake onto a bitmap display and also keep a list of either positions or directions, and figure that the snake collides with itself if the bitmap is set on the spot the head is about to reach. This would avoid any requirement for iterating through the snake segments on every frame if the chip keeps track of both the head and tail positions.

If your goal is a game that outputs a 80x50 grid on video, you need to minimize the number of registers and quantity logic of used by the game (e.g. not using 4000 bits of RAM for the display), and if the maximum snake length is e.g. 512 segments, you could use a 512x2 shift register to keep track of the snake's segments, an 80-bit "universal" shift register (which on each cycle can either be cleared, rotate left, rotate right, or stay put) for rendering the next display line, and an 80-bit shift register to buffer data going out to the display. So slightly less than 1200 bits of storage total.

An arrangement such as I describe should be workable for NTSC video with about a 2MHz clock. A collision that occurs between a snake's head and another segment would be detected on the scan line containing the snake's head when the hardware tries to set the line-buffer bit for the appropriate segment. If one uses a clock that's massively faster than 2MHz one could eliminate the need for some of the extra storage, but since the bulk of the storage would be the two bits per segment for the snake I don't think there's much room for savings.

BTW, if one wants to make things look a little nicer one could use 80x5 shift registers for the line buffers and keep track for each cell of the direction via which it was entered and via exited. Add in some ROM and an output register and one could animate the snake's body so it would appear to move smoothly.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.