Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
<WRAP centeralign round box>
<WRAP><color red><fs 200%>Corning Community College</fs></color></WRAP>
<WRAP><fs 150%>CSCS2330 Discrete Structures</fs></WRAP>
</WRAP>

======PROJECT: Flexible Observant Mind (FOM0)======

=====Objective=====
Using the TIC-80 fantasy console simulator on your pi, implement a program that performs a sprite-based animated count of a set of LEDs (a minimum of 9) in binary from 0 through the maximum value able to be represented therein.

The three approaches I'd like for you to implement are those of:

  * bitwise-logic
  * remainders (the division approach when converting base 10 to base 2)
  * the "contains" approach, resulting in a progressive subtraction

The universal restriction: you must not have <nowiki>2^number of LEDs</nowiki> if statements, one per potential number. That is NOT a feasible way to carry out this approach.

You may want to work out these approaches by hand on paper to understand their details and steps of progression, then to implement them.

Additionally, the entire class will be participating in documenting and filling out this project page. It is the responsibility of EACH class member to:

  * ask copious, clarifying questions (so you can better add content)
  * craft a coherent and organized document, with information located under pertinent headings
  * explain the fundamentals of the process, conceptual background, algorithmic approach, and you can even suggest particulars related to TIC-80 (certain functions that might prove useful- individual, unrelated snippets to do things like capturing time or displaying text, etc.)
  * to get full credit, each individual that submits must perform no fewer than 4 changes to this document (as viewable from the wiki revision system). Failure to do so will result in documentation penalties being applied.

=====Specifications=====

====Process====

===A Note on the Binary Number System===
The binary number system is much like the base-10 system we know and love, except there is one small difference; binary is base-2. Thus, the only individual digits available are 1's and 0's. For counting purposes, it is incremented by one on the right side, flipping the left bit once it surpasses 1. This is kind of hard to explain over words alone, so observe this example:
<code>
0000 - 0
0001 - 1
0010 - 2
0011 - 3
0100 - 4
0101 - 5
0110 - 6
0111 - 7
1000 - 8
1001 - 9
1010 - 10
1011 - 11
1100 - 12
1101 - 13
1110 - 14
1111 - 15
</code>
From here, you may have noticed a pattern; one can calculate the number of individual base-10 numbers from the length of the respective binary number. For example, the above binary integer had 4 digits. 4^2, in base-10, is 16, and there are 16 respective base-10 integers in the example. So, for a minimum of 9 digits in this project, one can fit an equivalent 2^9 base-10 integers, or 0 - 511.

===Successive Containment===

In this method, one ends up doing some fun progressive subtraction. This method essentially breaks down a decimal number into its binary places and asks for each place whether it exists in that number. In binary, as we've all *probably* learned by now, each place is 2 times that of the previous place. I.E. 16, 8, 4, 2, 1. We start with the greatest place, and work our way down, asking if the decimal number associated with that place exists in the decimal number we are converting to binary and then acting correspondingly. If we were working with 4 bits, it would look something like this:
<code>
Given the number 13, we first figure out whether there is a 1 in the 8's place.
Essentially, we ask the question "Is 13 - 8 >= 0?" If so, we do that subtraction,
and then we set that bit (the 8's place) to 1.
    
    1---
    
Now we are left with the remaining 5, and we are now checking the 4's place.
"Is 5 - 4 >= 0?" If so, we subtract and set the bit to 1.
    
    11--
    
With 1 remaining we check the 2's place.
"Is 1 - 2 >= 0?" If so, we subtract and set the bit to 1.
    
    110-
    
With 1 remaining we check the 1's place.
"Is 1 - 1 >= 0?" If so, we subtract and set the bit to 1.
    
    1101
</code>
    
Obviously, this should be scaled up for fom0 purposes, because we will be counting to higher numbers than 15. The logic however remains the same, we just start by subtracting higher numbers for higher places.

One more thing to note, conditions like "Is 5 - 4 >= 0?" can be simplified to "Is 5 >= 4?". Both are accurate ways of looking at this method. The point of this method is to see whether a particular number contains another number. If you can subtract one number from another then that number must contain what is subtractable. If a number is greater than or equal to another number, then it must contain the number it is greater than or equal to.

===Modulo Conversion===

In this method, which is at its core a conversion from base 10 to base 2, the input number is repeatedly divided and rounded down by the base until each of the binary digits are obtained and the input becomes 0. 

For example:
<code>
Given the number 13:

                            13 % 2 = 1
                    13 / 2 = 6 % 2 = 0
            13 / 2 = 6 / 2 = 3 % 2 = 1
    13 / 2 = 6 / 2 = 3 / 2 = 1 % 2 = 1
    
                                  1101
One could shorten it like so:

                        13 / 1 % 2 = 1
                        13 / 2 % 2 = 0
                        13 / 4 % 2 = 1
                        13 / 8 % 2 = 1
    
                                  1101
</code>

Since this method relies on repetition until some condition is met, it will occur within a loop after declaring the output variable (which will be a string for this example):
<code>
out = ""
while (input != 0):
</code>
Within this loop, the first step will be to obtain the smallest binary digit from the input number, which we can do via modulo:
<code>
...
  // Insert the smallest obtainable digit at the start of out
  out = (input % 2) + "" + out
  // And truncate input, removing the lower obtained portion
  input = roundDown(input / 2);
</code>
By performing that operation until input reaches 0, digits will be successively added until the full binary representation is ascertained.

===Bitwise Incrementation===
A computer thinks of every number as a binary number. Thus, we can take advantage of that by using some binary specific operations to convert decimal numbers into binary numbers to display. The computer knows the binary conversion of the incrementing counter number, what we need to do is force the extraction of said number.

For example, Given the number 13:

(Remembering that we are just using the AND on ‘13’ But the computer sees it as binary)

<code>
13 == 1101
  AND 0001
      ————
      0001
</code>

Now we know whether the first bit should be set.
From there, we right shift it and AND it against the same 0001:

<code>
      0110
  AND 0001
      ————
      0000
</code>

Now we know the second bit is zero, so the counter should show that.
Next, we right shift and AND yet again.

<code>
      0011
  AND 0001
      ————
      0001
</code>

Now we have the third bit as being on.
Right shift and AND:

<code>
      0001
  AND 0001
      ————
      0001
</code>

Blazam! Now we have an ‘on’ state for the final bit, and therefore a known state for every bit in the number 13. For larger numbers like the ones we will see on fom0, we will scale this method up. 

In lua, we will need to take a look at the current bits of the number being converted to binary. A really easy way to do this is with the following syntax "if (number & 1)==1  then". This if statement checks if the furthest bit on the right of the current number being assessed is 1. We can then shift the bits of the current number being assessed to the right and repeat the if statement. 
====Display====

In terms of display, the basics are as such: two sprites should exist, one which represents an off state (this could also be a blank / no sprite), and one which represents an on state. By showing either of these two sprites as part of some ordered set, a binary number can be represented as if it were 1s and 0s.
=====References=====

https://github.com/nesbox/TIC-80/wiki

https://en.wikipedia.org/wiki/Binary_number

https://en.wikipedia.org/wiki/Bitwise_operation

https://www.youtube.com/watch?v=kVvP5MNIND4

https://www.youtube.com/watch?v=rsxT4FfRBaM

http://lua-users.org/wiki/BitwiseOperators
=====Submission=====

To submit the game file, our "tic" file, the file must be added to your lab46 somehow. This can be achieved through FTP software, such as FileZilla, or more easily by putting the file onto your Pi then pushing to your repo and pulling from lab46.

//Of course, if you are using the TIC-80 application on your Pi then the file will exist there when saved.//

To submit this project using the **submit** tool, run the following command at your lab46 prompt:

<cli>
lab46:~/src/SEMESTER/DESIG/fomX$ submit DESIG fomX GAMENAME.tic
Submitting DESIG project "fomX":
    -> GAMENAME.tic(OK)

SUCCESSFULLY SUBMITTED
</cli>

NOTE: "GAMENAME" here is the name of your game. Please do not literally submit a tic file named "GAMENAME", come up with a creative name for your game.

I'll be looking for the following:

<code>
78:fom0:final tally of results (78/78)
*:fom0:no errors, program runs without issue in TIC-80 [13/13]
*:fom0:specified algorithms are implemented and functional [39/39]
*:fom0:display of sprite based, animated count [13/13]
*:fom0:project page contributions as per project specifications [13/13]
</code>

Additionally:
  * Solutions not abiding by **SPIRIT** of project will be subject to a 25% overall deduction
  * Solutions not utilizing descriptive why and how **COMMENTS** will be subject to a 25% overall deduction
  * Solutions not utilizing **INDENTATION** to promote scope and clarity will be subject to a 25% overall deduction
  * Solutions lacking **ORGANIZATION** and are not easy to read (within 90 char width) are subject to a 25% overall deduction
Lab46 Wiki

User Tools

Site Tools

Page Tools
