CPPND: Capstone Snake Game Example

This is a repo for the Capstone project in the Udacity C++ Nanodegree Program with snakebot controlled by the computer using the A* search algorithm. The code for this repo was inspired by this excellent StackOverflow post and set of responses.

New Features

The idea of added features are from the previous project Build An OpenStreetMap Route Planner and Concurrent Traffic Simulation. The snakebot follow the gray route planned by A* algorithm, and will stop immediately upon detecting a red light at an the intersection. It will move again once the light turns green.

By the way, I kept the code for the player-controlled snake in the program, but I commented it out. If you want to compete with the snakebot, feel free to remove the comments.

Additionally, you can build your own C++ application or extend the work, for example replacing the A* search algorithm with AI approach . This project will demonstrate that you can independently create applications using a wide range of C++ features.

The following diagram is the schematic of my program. The colored blocks indicate the changes I made: light blue for small changes and dark blue for the main changes where I implemented the new features.

Criteria Fullfillment

Loops, Functions, I/O - meet at least 2 criteria

• The project demonstrates an understanding of C++ functions and control structures.
  • snakebot.h, snakebot.cpp, intersection.h, and intersection.cpp files demonstrate the well-structured code and a variety of control structures.
• The project reads data from a file and process the data, or the program writes data to a file.
• The project accepts user input and processes the input.
• The project uses data structures and immutable variables.
  • The delta variable (in class Astar in snakebot.h) and intersectionLocation variable (in class intersection in intersection.h) are both vector with const int element.

Object Oriented Programming - meet at least 3 criteria

• One or more classes are added to the project with appropriate access specifiers for class members.
  • The classes in snakebot.h and intersection.h hold variables and methods, and explicityly specified as public and private.
• Class constructors utilize member initialization lists.
  • The snakebot class in snakebot.h and snakebot.cpp use the similar way to utilize member initialization list.
• Classes abstract implementation details from their interfaces.
  • The concise comments are wrote in the snakebot.h and intersection.cpp.
• Overloaded functions allow the same function to operate on different parameters.
• Classes follow an appropriate inheritance hierarchy with virtual and override functions.
  • The UpdateDirection is a virtual function defined in Snake class, and being overrided in Snakebot class.
• Templates generalize functions or classes in the project.
  • The Node class in snakebot.h is declared with a template named T.

Memory Management - meet at least 3 criteria

• The project makes use of references in function declarations.
  • The setters and operators in Node class in snakebot.h use pass-by-reference method.
• The project uses destructors appropriately.
  • The destructor of Astar in snakebot.cpp delete the dynamically allocated memory appropriately.
• The project uses scope / Resource Acquisition Is Initialization (RAII) where appropriate.
  • Acquiring resources for nodeGrid in Astar constructor and Releasing the resources in destructor in snakebot.cpp.
  • Setting thread barriers in destructor of class Snakebot and Intersection.
• The project follows the Rule of 5.
• The project uses move semantics to move data instead of copying it, where possible.
  • The move semantics is used when the snakebot plan new route after finding the food in Game::Update() in game.cpp.
• The project uses smart pointers instead of raw pointers.
  • The unique pointer of astar class is created in the beginning of Sankebot::PlanRoute(SDL_Point food) in snakebot.cpp.

Concurrency - meet at least 2 criteria

• The project uses multithreading.
  • The multi-threading is implementing in Snake::simulate() in snakebot.cpp for executing the traffic light and update snakebot in parallel.
• A promise and future is used in the project.
• A mutex or lock is used in the project.
  • The lock is used in several function in Snakebot class such as Snakebot::PlanRoute(), Snakebot::UpdateDirection(), Snakebot::UpdateHead(), and Snakebot::UpdateBody to protect the path data to ensure it is safely written and read.
• A condition variable is used in the project.

Dependencies for Running Locally

• cmake >= 3.7
  • All OSes: click here for installation instructions
• make >= 4.1 (Linux, Mac), 3.81 (Windows)
  • Linux: make is installed by default on most Linux distros
  • Mac: install Xcode command line tools to get make
  • Windows: Click here for installation instructions
• SDL2 >= 2.0
  • All installation instructions can be found here

  Note that for Linux, an apt or apt-get installation is preferred to building from source.

• gcc/g++ >= 5.4
  • Linux: gcc / g++ is installed by default on most Linux distros
  • Mac: same deal as make - install Xcode command line tools
  • Windows: recommend using MinGW

Basic Build Instructions

1. Clone this repo.
2. Make a build directory in the top level directory: mkdir build && cd build
3. Compile: cmake .. && make
4. Run it: ./SnakeGame.

CC Attribution-ShareAlike 4.0 International

Shield:

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.