Coding INDOOR NAVIGATION with A* Pathfinding

all right today we are finally gonna do some indoor navigation get hyped so first of all we need to scan all the areas that a user may localize in so we'll scan all the entrances and common areas now we'll walk to our destination and drop breadcrumbs as we go so we have a clear walkable path we can mark the destination and then keep walking to all of our start points to make sure that they also have a path to the destination so now we save the map and it writes everything to the server now we can open that app in any of the areas that we previously scanned and the device will localize the a-star navigation algorithm run to find us the shortest path to our destination using all the nodes that we saved previously we don't show the whole path because we don't want everything to show through the walls it's cheat occlusion in a way we'll just activate the next node in the path as we walk to our destination all right sorry this video took so long I've had the project done for a while but I've just been drowning in homework lately anyway in the last video I naively committed to doing some indoor navigation having no idea how the solution was actually going to pan out the first thing we need to consider is how are we going to localize our device indoors without using GPS this is the same problem that prevents multiplayer AR experiences from being easy to do basically we need to figure out a way to map an indoor area then when we start to app on the phone it needs to be able to figure out where it is relative to that map so research tells us that there's a few ways to do this we can use Bluetooth beacons we can do our SSI fingerprinting or we can use computer vision by way of an augmented reality SDK to map the environment with Bluetooth beacons the basic idea is to put a bunch of them in an area and then calculate your position based on the IDs and receive signal strength or our SSI of the Bluetooth beacons but that's out just because it's out we're not doing that our SSI fingerprinting on the other hand uses Wi-Fi and the basic idea is to map an area by walking around and taking our SSI readings everywhere creating a grid of nodes that each have a signal strength and a MAC address attached to them so when you open up your phone you can use the current MAC address of the connected access point and it's our SSI value to figure out which node you're closest to while we aren't going to do this today I am doing a project on this for my wireless networking class so we'll probably explore this in a future video my experience with this so far is that it's really not accurate and also it only works on Android because iOS doesn't give you access to networking information the third method is what we're going to use today and that is using an augmented reality SDK to map an area with computer vision and then save that information so we can relocate it later a our core for Android has their cloud anchor feature and AR kit has their a our world map feature for saving maps AR core allows their cloud anchors to be viewed from iOS so I thought this would be a good cross-platform solution once we have a method for localization we can move to the next step which is we need to be able to save a walkable path within the map that leads to our destination so this way we can display the best path for the user the easiest way to do this seems to be dropping waypoints as you map the area like breadcrumbs except for you drop them along every possible passageway it quickly becomes apparent that you need some kind of cloud storage not only to save the map but also to save X number of waypoints and their locations inside each map now I remembered my buddy salty telling me about an SDK called place note I figured I better investigate that before I start because it's super important to check out all possible solutions before you embark on a project because you don't want to end up reinventing the wheel it turns out place note is an SDK for creating persistent AR that integrates with AR kit and also has a nice cloud-based solution that goes along with it so this is great for making multiplayer experiences for tagging messages in particular areas or in our case indoor navigation so this is different than using a our kit 2.0 and there a our world map because place note takes care of cloud storage for us so as we said before you need to be able to upload and store information in addition to your map of the room place note allows you to easily serialize and upload content along with your map now we could make this app with AR core and their cloud anchor feature but the same problem exists where we need to create our own kind of like server back-end for storing the map and its associated data also AR court only allows you to store your cloud anchors for like 24 hours which is okay for making multiplayer experiences but it doesn't really work for indoor navigation so I ended up making a little indoor navigation demo with place--not and that's what I'm going to show you guys how to use now unfortunately it's only gonna work for iOS don't be mad place note is supposed to come out with an Android solution but I exactly what if you want to talk to someplace no devs or you want to annoyed the team about the Android version check out place note comm slash slack now I am super busy with school right now but I should be done like early December so I'll look into doing an Android version at that point whether it's with place note or AR core so stay tuned for that anyway to get this app working on your phone we first need to get the project so go to my github and find the indoor nav place note project download that and open it up in unity my last commit was with unity version 20 18.3 so try to use that version if you can to avoid problems now we need to sign up for place note and get a license key so go to place note comm and create an account once you're logged in go to API keys and create a new key copy that key to your clipboard if you click on the places tab this is the cloud storage area that I was talking about earlier you can see all the different maps that you saved and if you click on one you can see all the metadata that gets saved with each map like your GPS location and even the JSON that contains your Waypoint information like type and position if we go back to unity you can go to place note and scenes to find the place note sample scene if you build this out to your phone you can see what place note is capable of this scene allows you to save and load multiple maps so in my project I basically split this into two scenes one for creating a map and one for reading the map I figured you guys would be using this for like school projects and stuff so you yourselves could use the create map scene to make the map and then for whoever's gonna actually use and evaluate it you would just build them out the read map scene hopefully that makes things easier so if we go to the scenes folder you'll see a create map scene and a read map scene before we forget let's open up each one and paste in your license key on each place note camera manager object open up the create map seen this scene allows you to save a map and drop all the waypoints so if we open up that create map script on the main panel this is where all the magic happens now you can save multiple maps with place note but in this implementation I just rewrite the same one every time for simplicity in the UI when you use the scene make sure to get a good scan of the room where you start and then hit create a map this allows you to start dropping waypoints as you move which happens down in the update function of the create Maps es script it should be noted that you only have to fully scan rooms in which a user may localize in so in hallways and corridors you don't have to worry about getting any feature points now if we go to the read map scene and find the main panel the read map script is where the map gets loaded from your place note account if you go down to the find map function you will see that I'm using Lib place note to search for a map by name but one of the coolest things about place note is that this search Maps function has a bunch of overloads one of which is that you can search for a map based on GPS coordinates I thought this was super cool if you have a bunch of places mapped because the user doesn't have to find the map they're closest to you can do it all behind the scenes now one important thing that I forgot to do was give the user some feedback when localization occurs right now only the first arrow shows up which is only useful if you're looking in that direction so if you look to the bottom there's a non status change callback that gets that loads the shapes upon localization it may be useful to display some kind of message to the user when that occurs so that they know to look around for the first arrow now the last important piece of this project is the path finding piece so if we go to the scripts folder you will see an a-star script this is just an implementation of the a-star path finding algorithm that takes in a list of nodes as well as a start node and a destination node it then outputs the shortest path between the two the node script goes on each Waypoint and is responsible for finding all of its nearest neighbors the a-star script uses this information when traversing different paths before it finds the shortest one so the knife controller script is what goes on the main camera in the read map scene and it's responsible for initiating the navigation and it uses collisions to activate the next node in the path as you walk around so one big issue I was having was that the a-star algorithm wouldn't always return a path this was because each node didn't always have neighbors that led to the destination so to alleviate this issue I recursively run the a-star algorithm increasing the distance that each node searches for its neighbors until a solution is reached so if you don't create a destination node when you're creating a new map you will have many problems if you want to test the navigation stuff I have a game object that's currently disabled in the scene just enable that and click play and you can move the camera around to see the behavior in the editor don't forget to disable this before you build or else the app will basically explode now to get this on your phone go to player settings and make sure you put something in the bundle identifier also make sure you have something for a camera usage description as well as a location usage description so when you open it up in Xcode everything should be set but at some point I updated the place note SDK mid project and the link to the place no framework broke so make sure to relink that also make sure that you're not on iOS 12 I've only tested this on iOS 11 and on their website it does not say anything about iOS 12 support so if you are on iOS 12 just be wary of that issue alright so that's it that's all I got for today let me know in the comments if this helped you out if you have any questions let me know and it's gonna be a while until I get to do my next video but I'll probably try to explore some kind of solution like this for Android whether it's with a our core or place note or maybe we try that our SSI fingerprinting stuff for Android so not entirely sure but let me know in the comments what you guys want to see and with that I'm gonna go torture myself with some more homework so we'll see you in the next one goodbye [Music] [Music] [Music]

Channel: MatthewHallberg

Views: 130,296

Keywords: how to augmented reality, augmented reality, unity augmented reality, Indoor navigation, ar tutorial, augmented reality tutorial, ar, mixed reality, virtual reality, A* Pathfinding, A* algorithm

Id: VOMysKbDNxk

Length: 10min 24sec (624 seconds)

Published: Tue Oct 23 2018