Week 26 - Pathfinding and Back-end
The user interface of our application is coming close to our wishes and we decided to move on to the next part of development; the pathfinding and back-end part of our application. We made the choice to implement pathfinding with GameplayKit, a library offered by Apple. Promoted for games, there is actually no obstacle for using it as a visualisation tool for our indoor localization application.
GameplayKit is a collection of following functionalities:
Agents, Goals and Behaviours
GameplayKit offers reusability and facilitates the separation of aspects of your game like UI, AI, physics and sounds.
Promoted heavily in the several Apple tutorials of GameplayKit, we discovered a new design pattern called entities and components. The entity-component design pattern is an architecture that favors composition over inheritance. Developing applications is rarely done in a waterfall model anymore. Updates are done all the time, based on developer and user feedback. It’s not possible to structure an application correctly from the start. Even when you did, your best seller Alien Massacre XD would surely deserve an add-on, why would you rewrite the engine from scratch?
For developing applications that will evolve over time, inheritance based architecture hinders easy changes of the application architecture. That’s why we decided to code our application, at least for the visualisation part, in an entity-component architecture.
An entity is a general type for objects relevant to your game. Those entities gets their functionality by components. A component is an object that handles a specific and limited aspect such as sprite rendering, shooting, movement,...
Short said, it is a way to organize your code based on what each game object does instead of what each game object is.
If you are interested in the subject, I found this article very explanatory http://gameprogrammingpatterns.com/component.html
The other topic of this week is pathfinding. What can be so difficult to move someone from A to B? In an ideal world you would do everything as the crow flies. But sadly, indoor localization is more complex than that.
Based on some serious research we found out that we had the following options;
Break our heads and try to build an algorithm on our own (Haha)
Implement and use an existing pathfinding algorithm like A* (pronounced A star) or Dijkstra (hihi)
Use GameplayKit (hoho ... hum what?)
You already know the answer; We choose to use GameplayKit. Underneath the surface, GameplayKit is using A*. Roughly all you have to do is to implement a grid and run a function like findTheBestPathFromThisPointToThatPoint() to use the pathfinding algorithm. That’s awesome!
We don’t want to overcomplicate things so we made the decision to use a two-dimensional world. What does that mean? It’s meaning that we are mapping our environment on a x-y representation like a chess board. Each x-y spot is a navigable point. An empty x-y spot is a point where you cannot navigate too. Could be an obstacle or a wall for example.
Starting from here, you have two things to implement to visualise pathfinding.
A visual representation of a 2d grid
A programmatic representation of a 2d grid
Lucky us, Apple provides libraries for both. For the visual part there is SpriteKit and for the programmatic part there is………….yes you guessed it…….. GameplayKit.
Based on Apple documentation, a programmatic representation of a 2D grid can be achieved with a GKGridGraph. It’s on that grid that you achieve the pathfinding function findPathFromNode(currentNode, destinationNode)
And that’s basically it… Here is the result.
Believe me or not, I’m really happy this is working. Of course the navigation and beacons are still to be implemented in this system but we are getting closer!
For the back-end part of our application, we are using Parse. Again, a tool that let us focus on the important problems of our application to solve. It facilitates a lot of server-side stuff like accounts and databases. We are using a back-end system to determine which places are shown in the applications. Each place would have an ID linked to his environment (An airport? A school? A Museum?) Based on the beacon signal received when opening the application, we are able to show those navigable spots like the toilets and shops.
We know beacon technology is still in their early days and article like those https://www.brooklynmuseum.org/community/blogosphere/2015/02/04/the-realities-of-installing-ibeacon-to-scale/ don’t encourage us to use them for such use. But the amount of knowledge we already gained only motivates us to continue. If beacons are still not viable for large scale areas, they could enhance the experience of visitors, even in small areas.