Overview
Overview
Overview
Overview
Overview
Overview
Overview
Overview
Overview
A small game created so I could put my knowledge of networking to the test. It is a Hybrid Client -Server model with one instance of the application acting as the server and also running a local client and any others just acting as clients connected to the server. Each client has a player character and it's job is top take any inputs received and send them to the server in a input package which consists of a vector and an ID. The majority of processing then happens in the server and the current state of the game is sent back to the clients which update accordingly.
By using differing hardware and using Clumsy, a third party networking tool, to simulate different network conditions I was able to get a good feel on how the application worked and how to improve it. What follows is a short summary on how the application behaves.
Due to the usage of prediction and interpolation gameplay was possible until latency hit 500ms. Some jittering is visible when there is a high amount of duplicated or dropped packets however as the application uses a TCP connection. Due to this any out of order packets do not have an effect. Some loss of sync can happen due to how SFML handles window focus but nothing major. Overall, a user will need an average or above broadband connection to use this application in an error free manner but if that exists it should work quite reliably.
A* Pathfinding
Engine/Framework:
Visual Studio 2015
Coding & Scripting Languages:
C++
Target Platform:
Windows PC
Development Time:
1 month
Completed On:
2016
Goals and Objectives
1. Implement shortest-path algorithms in C++ • Dijkstra’s Algorithm. • A* (Astar) & variants
2. Justify use of data structures used within the algorithms.
3. Compare performance of previously implement solutions
Reasons for Shortest-Path
• Shortest-path algorithms integral for a games developer.
• Multiple variants allows for performance testing.
• Project I’m working on requires a pathfinding solution.
• Usage of grids instead of general purpose graphs
Choosing data structures
Using arrays to hold information such as the grid, path, open nodes and closed nodes. Unlike vectors arrays need to have a constant size meaning I could not change them during runtime. I could directly access an element of an array from memory while that would not be as simple in a vector or other container classes. Arrays are more memory compact.
Using a priority queue for the main data holder.
-
Insertion and extraction less time consuming (from O(n) to O(1)).
-
Automatic ordering of data makes calculating path much faster.
-
Most of the program time is spent making a new node and then deleting it.
-
40% for making a new node, 18% for deletion versus only 0.7% for push back and 7% for heap adjustments.