Revision 3:2fe73b263a9a, committed 2020-11-23

Comitter:

congvu

Date:

Mon Nov 23 05:54:49 2020 +0000

Parent:

2:4947d6a82971

Commit message:

ECE2035;

Changed in this revision

diff -r 4947d6a82971 -r 2fe73b263a9a graphics.cpp
--- a/graphics.cpp	Fri Oct 23 16:30:18 2020 -0400
+++ b/graphics.cpp	Mon Nov 23 05:54:49 2020 +0000
@@ -8,6 +8,38 @@
 
 #include "globals.h"
 
+#define YELLOW 0xFFFF00
+#define BROWN  0xD2691E
+#define DIRT   BROWN
+
+const char head[121] = {
+    'G','G','G','G','G','G','G','G','G','G','G',
+    'G','G','G','G','G','G','G','G','G','G','G',
+    'G','R','R','R','G','G','R','R','R','G','G',
+    'G','R','R','R','G','G','R','R','R','G','G',
+    'G','R','R','R','G','G','R','R','R','G','G',
+    'G','G','G','G','G','G','G','G','G','G','G',
+    'G','R','R','R','G','G','R','R','R','G','G',
+    'G','R','R','R','G','G','R','R','R','G','G',
+    'G','R','R','R','G','G','R','R','R','G','G',
+    'G','G','G','G','G','G','G','G','G','G','G',
+    'G','G','G','G','G','G','G','G','G','G','G',
+    };
+ 
+const char tail[121] = {
+    'G','G','G','G','G','G','G','G','G','G','G',
+    'G','G','G','G','G','G','G','G','G','G','G',
+    'G','Y','Y','Y','G','G','G','Y','Y','Y','G',
+    'G','Y','Y','Y','G','G','G','Y','Y','Y','G',
+    'G','Y','Y','Y','G','G','G','Y','Y','Y','G',
+    'G','G','G','G','G','G','G','G','G','G','G',
+    'G','G','G','G','G','G','G','G','G','G','G',
+    'G','Y','Y','Y','G','G','Y','Y','Y','G','G',
+    'G','Y','Y','Y','G','G','Y','Y','Y','G','G',
+    'G','Y','Y','Y','G','G','Y','Y','Y','G','G',
+    'G','G','G','G','G','G','G','G','G','G','G',
+    }; 
+    
 void draw_nothing(int u, int v)
 {
     uLCD.filled_rectangle(u, v, u+10, v+10, BLACK);
@@ -32,7 +64,7 @@
 
 void draw_wall(int u, int v)
 {
-    uLCD.filled_rectangle(u, v, u+10, v+10, BLACK);
+    uLCD.filled_rectangle(u, v, u+10, v+10, LGREY);
 }
 
 void draw_plant(int u, int v)
@@ -42,7 +74,7 @@
 
 void draw_goodie(int u, int v)
 {
-    uLCD.filled_rectangle(u, v, u+10, v+10, GREEN);
+    uLCD.filled_rectangle(u, v, u+10, v+10, 0xD2691E); //DIRT
 }
 
 void draw_snake_body(int u, int v)
@@ -54,15 +86,27 @@
 {
      //May need to design a snake head sprite
      //Tile still need to be designed on paper
-
+    
     uLCD.filled_rectangle(u, v, u+10, v+10, GREEN);
+    draw_img(u,v, head);
+//    uLCD.filled_rectangle(u+1, v+1, u+3, v+3, RED);
+//    uLCD.filled_rectangle(u+7, v+1, u+9, v+3, RED);
+//    uLCD.filled_rectangle(u+1, v+7, u+3, v+9, RED);
+//    uLCD.filled_rectangle(u+7, v+7, u+9, v+9, RED);
+    
 }
 
 void draw_snake_tail(int u, int v)
 {
      //May need to design a snake tail sprite
      //Tile still need to be designed on paper
+    
     uLCD.filled_rectangle(u, v, u+10, v+10, GREEN);
+    draw_img(u,v, tail); 
+//    uLCD.filled_rectangle(u+1, v+1, u+3, v+3, 0xFFFF00); //YELLOW
+//    uLCD.filled_rectangle(u+7, v+1, u+9, v+3, 0xFFFF00);
+//    uLCD.filled_rectangle(u+1, v+7, u+3, v+9, 0xFFFF00);
+//    uLCD.filled_rectangle(u+7, v+7, u+9, v+9, 0xFFFF00);
 }
 
 

diff -r 4947d6a82971 -r 2fe73b263a9a hash_table.cpp
--- a/hash_table.cpp	Fri Oct 23 16:30:18 2020 -0400
+++ b/hash_table.cpp	Mon Nov 23 05:54:49 2020 +0000
@@ -1,55 +1,41 @@
-// Copyright 2020 Georgia Tech.  All rights reserved.
-// The materials provided by the instructor in this course are for
-// the use of the students currently enrolled in the course.
-// Copyrighted course materials may not be further disseminated.
-// This file must not be made publicly available anywhere.
 /*
- Student Name:
- Date:
- 
+Student Name: Cong Vu
+Date: 11/01/2020
 =======================
 ECE 2035 Project 2-1:
 =======================
 This file provides definition for the structs and functions declared in the
 header file. It also contains helper functions that are not accessible from
 outside of the file.
- 
 FOR FULL CREDIT, BE SURE TO TRY MULTIPLE TEST CASES and DOCUMENT YOUR CODE.
- 
 ===================================
 Naming conventions in this file:
 ===================================
 1. All struct names use camel case where the first letter is capitalized.
-  e.g. "HashTable", or "HashTableEntry"
- 
+e.g. "HashTable", or "HashTableEntry"
 2. Variable names with a preceding underscore "_" will not be called directly.
-  e.g. "_HashTable", "_HashTableEntry"
- 
-  Recall that in C, we have to type "struct" together with the name of the struct
-  in order to initialize a new variable. To avoid this, in hash_table.h
-  we use typedef to provide new "nicknames" for "struct _HashTable" and
-  "struct _HashTableEntry". As a result, we can create new struct variables
-  by just using:
-    - "HashTable myNewTable;"
-     or
-    - "HashTableEntry myNewHashTableEntry;"
- 
-  The preceding underscore "_" simply provides a distinction between the names
-  of the actual struct defition and the "nicknames" that we use to initialize
-  new structs.
-  [See Hidden Definitions section for more information.]
- 
+e.g. "_HashTable", "_HashTableEntry"
+Recall that in C, we have to type "struct" together with the name of the struct
+in order to initialize a new variable. To avoid this, in hash_table.h
+we use typedef to provide new "nicknames" for "struct _HashTable" and
+"struct _HashTableEntry". As a result, we can create new struct variables
+by just using:
+- "HashTable myNewTable;"
+or
+- "HashTableEntry myNewHashTableEntry;"
+The preceding underscore "_" simply provides a distinction between the names
+of the actual struct defition and the "nicknames" that we use to initialize
+new structs.
+[See Hidden Definitions section for more information.]
 3. Functions, their local variables and arguments are named with camel case, where
-  the first letter is lower-case.
-  e.g. "createHashTable" is a function. One of its arguments is "numBuckets".
-       It also has a local variable called "newTable".
- 
+the first letter is lower-case.
+e.g. "createHashTable" is a function. One of its arguments is "numBuckets".
+It also has a local variable called "newTable".
 4. The name of a struct member is divided by using underscores "_". This serves
-  as a distinction between function local variables and struct members.
-  e.g. "num_buckets" is a member of "HashTable".
- 
+as a distinction between function local variables and struct members.
+e.g. "num_buckets" is a member of "HashTable".
 */
- 
+
 /****************************************************************************
 * Include the Public Interface
 *
@@ -59,8 +45,8 @@
 * correctness, but it is better than nothing!
 ***************************************************************************/
 #include "hash_table.h"
- 
- 
+
+
 /****************************************************************************
 * Include other private dependencies
 *
@@ -69,8 +55,8 @@
 ***************************************************************************/
 #include <stdlib.h>   // For malloc and free
 #include <stdio.h>    // For printf
- 
- 
+
+
 /****************************************************************************
 * Hidden Definitions
 *
@@ -79,40 +65,40 @@
 * available everywhere and user code can hold pointers to these structs.
 ***************************************************************************/
 /**
- * This structure represents an a hash table.
- * Use "HashTable" instead when you are creating a new variable. [See top comments]
- */
+* This structure represents an hash table.
+* Use "HashTable" instead when you are creating a new variable. [See top comments]
+*/
 struct _HashTable {
   /** The array of pointers to the head of a singly linked list, whose nodes
-      are HashTableEntry objects */
+  are HashTableEntry objects */
   HashTableEntry** buckets;
- 
+
   /** The hash function pointer */
   HashFunction hash;
- 
+
   /** The number of buckets in the hash table */
   unsigned int num_buckets;
 };
- 
+
 /**
- * This structure represents a hash table entry.
- * Use "HashTableEntry" instead when you are creating a new variable. [See top comments]
- */
+* This structure represents a hash table entry.
+* Use "HashTableEntry" instead when you are creating a new variable. [See top comments]
+*/
 struct _HashTableEntry {
   /** The key for the hash table entry */
   unsigned int key;
- 
+
   /** The value associated with this hash table entry */
   void* value;
- 
+
   /**
   * A pointer pointing to the next hash table entry
   * NULL means there is no next entry (i.e. this is the tail)
   */
   HashTableEntry* next;
 };
- 
- 
+
+
 /****************************************************************************
 * Private Functions
 *
@@ -130,10 +116,16 @@
 * @param value The value stored in the hash table entry
 * @return The pointer to the hash table entry
 */
-static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
- 
+static HashTableEntry* createHashTableEntry(unsigned int key, void *value) {
+
+  HashTableEntry* newEntry = (HashTableEntry*)malloc(sizeof(HashTableEntry));
+  newEntry ->key = key;
+  newEntry ->value = value;
+  newEntry ->next = NULL;
+
+  return newEntry;
 }
- 
+
 /**
 * findItem
 *
@@ -144,10 +136,25 @@
 * @param key The key corresponds to the hash table entry
 * @return The pointer to the hash table entry, or NULL if key does not exist
 */
-static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
- 
+ static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
+
+  //get which bucket
+  int bucketIndex = hashTable -> hash(key);
+
+  /**
+  * set thisNode to head of bucket we are looking in
+  */
+  HashTableEntry *thisNode = hashTable->buckets[bucketIndex];
+
+  while(thisNode) //while not null
+  {
+    if(thisNode -> key == key) return thisNode; //if equal, return that entry
+    thisNode = thisNode->next;//if not, get next entry
+  }
+  return thisNode; // return value, null if not found
 }
- 
+
+
 /****************************************************************************
 * Public Interface Functions
 *
@@ -163,40 +170,189 @@
     printf("Hash table has to contain at least 1 bucket...\n");
     exit(1);
   }
- 
+
   // Allocate memory for the new HashTable struct on heap.
   HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
- 
+
   // Initialize the components of the new HashTable struct.
   newTable->hash = hashFunction;
   newTable->num_buckets = numBuckets;
   newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
- 
+
   // As the new buckets are empty, init each bucket as NULL.
   unsigned int i;
   for (i=0; i<numBuckets; ++i) {
     newTable->buckets[i] = NULL;
   }
- 
+
   // Return the new HashTable struct.
   return newTable;
 }
- 
+
+
 void destroyHashTable(HashTable* hashTable) {
- 
+
+  int i;
+  //iterate through all all buckets, if 4 buckets, final value of i is 3
+  for (i = 0; i< (hashTable -> num_buckets); i++)
+  {
+    //if bucket's head entry is not null, delete all entries
+    if(hashTable -> buckets[i])
+    {
+      //keep track of currentNode
+      HashTableEntry* thisNode = hashTable -> buckets[i];
+      //keep track of nextNode so can iterate until there is only
+      //one entry left in bucket
+      HashTableEntry *nextNode = thisNode -> next;
+
+      while(nextNode)
+      {
+        //destroy thisNode and all its variables
+        free(thisNode -> value);
+        free(thisNode);
+        //update thisNode and nextNode
+        thisNode = nextNode;
+        nextNode = nextNode ->next;
+      }
+      //delete the final remaining entry, the tail
+      free(thisNode);
+    }
+  }
+  //destroy hashTable
+  free(hashTable);
+  return;
 }
- 
+
 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
+
+  //get which bucket to insert into
+  int bucketIndex = hashTable -> hash(key);
+
+  /**
+  * If there exists entry with passed in key, change its value
+  */
+  HashTableEntry *existNode = findItem(hashTable,key);
+  if(existNode)
+  {
+    //make copy of exisiting value
+    void* oldValue;
+    oldValue = existNode -> value;
+    //update value
+    existNode -> value = value;
+    //return value that is replaced
+    return oldValue;
+  }
+
+  //create new entry with specified key and value
+  HashTableEntry *thisNode = createHashTableEntry(key,value); //create new entry
+
+  //Edge case to check if malloc fails in createHashTableEntry, return NULL
+  if(!thisNode) return NULL;
+
+  /**
+  * Insert at head
+  * 1) change head of bucket to new entry
+  * 2) make new entry/head point to the changed head
+  */
+  thisNode -> next = hashTable->buckets[bucketIndex];
+  hashTable->buckets[bucketIndex] = thisNode;
+  return NULL;
 }
- 
+
+
 void* getItem(HashTable* hashTable, unsigned int key) {
- 
+
+  //check if entry/node exists by calling findItem()
+  HashTableEntry* existNode = findItem(hashTable,key);
+  if(existNode)
+  {
+    return existNode -> value;
+  }
+  return NULL;
 }
- 
+
 void* removeItem(HashTable* hashTable, unsigned int key) {
- 
+
+  //get which bucket
+  int bucketIndex = hashTable -> hash(key);
+
+  //get head of bucket
+  HashTableEntry *thisNode = hashTable -> buckets[bucketIndex];
+
+  //remove head
+  if(thisNode && thisNode -> key == key)
+  {
+    //get value of entry to be removed
+    void* removedEntryVal = thisNode -> value;
+    // update head
+    hashTable -> buckets[bucketIndex] = thisNode ->next;
+    //remove head entry
+    free(thisNode);
+    //return value of removed entry
+    return removedEntryVal;
+  }
+
+  //remove node other than head
+  while(thisNode && thisNode -> next)
+  {
+    //check if next entry is one to remove
+    if(thisNode -> next -> key == key)
+    {
+      //save entry to be removed
+      HashTableEntry* entryToRemove = thisNode -> next;
+      //save value of entry to be removed
+      void* removedEntryVal = entryToRemove -> value;
+      //remove entry from list by pointing around it and freeing it
+      thisNode -> next = thisNode -> next -> next;
+      free(entryToRemove);
+      //return value of removed entry
+      return removedEntryVal;
+    }
+    //if not, get next entry
+    thisNode = thisNode -> next;
+  }
+  //if entry not in table, return NULL
+  return NULL;
 }
- 
+
+
 void deleteItem(HashTable* hashTable, unsigned int key) {
- 
-}
\ No newline at end of file
+  //get which bucket
+  int bucketIndex = hashTable -> hash(key);
+
+  //get head of bucket
+  HashTableEntry *thisNode = hashTable -> buckets[bucketIndex];
+  if (findItem(hashTable,key) == NULL) return;
+
+  //delete head
+  if (thisNode && thisNode ->key == key)
+  {
+    //update the head
+    hashTable -> buckets[bucketIndex] = thisNode -> next;
+    //free value of head
+    free(thisNode -> value);
+    //free head entry
+    free(thisNode);
+    return;
+  }
+
+  //delete node other than head
+  while(thisNode && thisNode -> next)
+  {
+    //check if next entry is one to delete
+    if(thisNode -> next -> key == key)
+    {
+      //save entry to be deleted
+      HashTableEntry* entryToDelete = thisNode -> next;
+      //remove entry from list by pointing around it and freeing it
+      thisNode -> next = thisNode -> next -> next;
+      //free value
+      free(entryToDelete -> value);
+      //free entry
+      free(entryToDelete);
+      return;
+    }
+    //if not, get next entry
+    thisNode = thisNode -> next;
+  }
+}

diff -r 4947d6a82971 -r 2fe73b263a9a main.cpp
--- a/main.cpp	Fri Oct 23 16:30:18 2020 -0400
+++ b/main.cpp	Mon Nov 23 05:54:49 2020 +0000
@@ -111,8 +111,8 @@
     if(draw_option == FULL_DRAW) 
     {
         draw_border();
-        int u = 58;
-        int v = 56;
+        int u = 58;//58
+        int v = 46;//56
         draw_snake_head(u, v);
         draw_snake_body(u-11, v);
         draw_snake_tail(u-22, v);

diff -r 4947d6a82971 -r 2fe73b263a9a map.cpp
--- a/map.cpp	Fri Oct 23 16:30:18 2020 -0400
+++ b/map.cpp	Mon Nov 23 05:54:49 2020 +0000
@@ -17,6 +17,7 @@
     HashTable* items;
     int w, h;
 };
+#define NUM_BUCKETS 223
 
 #define NUM_MAPS 1
 static Map maps[NUM_MAPS];
@@ -34,6 +35,9 @@
  */
 static unsigned XY_KEY(int X, int Y) {
      // TODO: Fix me!
+         // int and unsigned are 4 bytes = 32 bits
+    unsigned int key = ((unsigned)X << 16) + (unsigned)Y;
+    return key;
 }
 
 /**
@@ -44,6 +48,7 @@
 unsigned map_hash(unsigned key)
 {
     // TODO: Fix me!
+    return key % NUM_BUCKETS;
 }
 
 void maps_init()
@@ -51,6 +56,12 @@
     // TODO: Implement!    
     // Initialize hash table
     // Set width & height
+        for (int i = 0; i < NUM_MAPS; i++) 
+        {
+        maps[i].w = map_width();
+        maps[i].h = map_height();
+        maps[i].items = createHashTable(map_hash, NUM_BUCKETS);
+        }
 }
 
 Map* get_active_map()
@@ -64,6 +75,11 @@
     return &maps[active_map];
 }
 
+Map* get_map(int m) 
+{
+    return &maps[m];
+}
+
 void print_map()
 {
     char lookup[] = {'W', 'D', 'P', 'A', 'K', 'C', 'N',' ','S'};
@@ -82,49 +98,62 @@
 
 int map_width()
 {
-
+        return 100;
 }
 
 int map_height()
 {
-
+   return 50;
 }
 
 int map_area()
 {
-
+    return map_width() * map_height();
 }
 MapItem* get_current(int x, int y)
 {
-    
+    Map* map = get_active_map();
+    MapItem* item = (MapItem*)getItem(map->items, XY_KEY(x, y));
+    return item;
 }
 MapItem* get_north(int x, int y)
 {
-    
+    Map* map = get_active_map();
+    MapItem* item = (MapItem*)getItem(map->items, XY_KEY(x, y + 1));
+    return item;
 }
 MapItem* get_south(int x, int y)
 {
-    
+    Map* map = get_active_map();
+    MapItem* item = (MapItem*)getItem(map->items, XY_KEY(x, y - 1));
+    return item;
 }
 
 MapItem* get_east(int x, int y)
 {
-    
+    Map* map = get_active_map();
+    MapItem* item = (MapItem*)getItem(map->items, XY_KEY(x + 1, y));
+    return item;
 }
 
 MapItem* get_west(int x, int y)
 {
-
+    Map* map = get_active_map();
+    MapItem* item = (MapItem*)getItem(map->items, XY_KEY(x - 1, y));
+    return item;
 }
 
 MapItem* get_here(int x, int y)
 {
-
+    Map* map = get_active_map();
+    MapItem* item = (MapItem*)getItem(map->items, XY_KEY(x, y));
+    return item;
 }
 
 void map_erase(int x, int y)
 {
-
+    Map* map = get_active_map();
+    removeItem(map->items, XY_KEY(x, y));
 }
 
 void add_wall(int x, int y, int dir, int len)