search

RandomSearch18 / a-level-project

Documentation for my A-level programming project
2 stars 0 forks source link

readme

Pedestrian routing using open map data

A-level Computer Science programming project

Contents

Analysis

Stakeholder identification

James

James is a member of my computing class and is interested in using OpenStreetMap (OSM) data for navigation, but needs a program that can reliably do this. He has already tried a few apps that use map data from OSM, so he will be able to provide insights to how my engine compares to results from other programs, as well as suggest areas where other engines fall short.

Andrew

Andrew is also in my computing class so I will have frequent contact with him. He uses pedestrian navigation for a variety of purposes in our local area, from going for runs in green spaces to goal-oriented navigation in a city centre. This wide range of uses in a small geographic area will be invaluable for rapid feedback cycles and adjustment of the routing engine during development. One use case he looks forward to trying is finding the optimal route to get to the local bakery from school. He wants to have easy-to read instructions and the total distance he'll have to walk.

Ili

Ili is a family member who will be able to provide feedback and ideas often. While he doesn't use pedestrian routing as often as my other stakeholders, he often uses navigation apps for driving and enjoys using maps. This means that he will certainly offer valuable opinions on map design, how intuitive the UI is, and the general user experience. He has highlighted the need for safety in pedestrian navigation, i.e. while crossing roads. My navigation app will provide him with an alternative to Google Maps for shorter journeys that better understands the pavements and crossings in our area.

Problem definition

A routing engine is a piece of software that calculates a route between two points in the world, following a pre-defined network of paths or roads. Routing engines first became commonly used with satnavs and similar automotive navigation systems (Wikipedia: w.wiki/BUn$) that provide live directions for driving.

Nowadays, "navigation apps" are the most common way to interact with a routing engine. They make the features of a routing engine accessible through a graphical interface that lets users enter a starting point and destination, from which a route will be calculated and plotted on a map.

Justification of computational approach

The task of finding an efficient route between two geographic locations has some complexities, such as the need for an algorithm to chose which paths to explore without knowing for sure which ones will be optimal. However, these challenges have successfully been overcome by a variety of programs that incorporate routing engines. This task is solvable with an algorithm because it of four characteristics: an initial situation, clear inputs and outputs, clearly defined logic, and a clear goal. These will be discussed in detail below.

Initial situation

The routing engine is provided with coordinates for a starting point, and coordinates for the ending point. The initial situation for the program will be a graph that represents a network of paths for the area that will be covered by the routing query. The graph will be generated by processing map data from OpenStreetMap with the following steps:

  1. Extract ways that represent a walkable section of a route, e.g. paths, roads, plazas. This will be done by checking for corresponding top-level tags, e.g. highway=footway.
  2. Also extract the nodes from each way. Untagged nodes that aren't intersections can be ignored.
  3. Use a recursive algorithm to walk through the extracted map data, building a graph where intersections and barriers are represented as graph nodes, and segments of walkable ways are represented as edges. A weight for each node and edge will be calculated to represent how desirable it would be to navigate that node, or walk along that edge.

Clear goal

Its goal is to provide the user with a real-world path that they can follow on foot to navigate from the start to the end point, as well as a series of steps that describe the route in text. The route should follow walkable map objects to ensure it makes sense as a route. The engine should generate routes that are desirable to a user looking to travel safely and efficiently (i.e. minimising the effort required to follow the route). To achieve this, the engine will follow the following principles:

In addition to the points above, the most desirable route for a user will depend on their own preferences and physical abilities. To accommodate this, the engine will be configurable to prioritise routes that are suitable for the specific user. Goals that should be configurable are:

Clear inputs and outputs

Users will interact with the routing engine through a basic web-based UI. There will be text fields to enter start and end points, using either coordinates or addresses (which are converted to coordinates using a geocoding API).

Once the route is calculated, it will be outputted by rendering it on a map rendered by the Leaflet library. It will also display a textual list of directions that can be followed.

Clearly defined logic

The front-end will use the Nominatim API to convert the inputted start and end locations to coordinates, or use coordinates directly if provided. The pair of coordinate pairs will then be passed to the routing engine.

The routing engine will use the routing graph to find the optimal route between the two points using a pathfinding algorithm, such as A*, to find a route that will be desirable for the user (as defined above).

Problem research

While I have a general mental idea of what the routing engine should accomplish, it's essential to research similar programs, as well as stakeholders, to gain a well-rounded idea of what features are most important for my program, as well as how to make the user interface as intuitive as possible for my target audience.

Initial stakeholder interviews

I will interview each of my stakeholders to gain an understanding of what they would like from a routing engine, and accompanying GUI. I plan to ask the following questions:

Question Justification
How often do you use an app or website to get directions? An idea of how frequently my app will guide my UI design, e.g. I may prioritise/deprioritise being able to quickly get directions
How often do you use an app or website to get directions for walking? To confirm or deny my hypothesis that predict that navigation apps will be used for pedestrian navigation much less frequently than for other modes of transport
In what situations are you more likely to use an app for pedestrian navigation? Tells me the specific situations that my app will likely be used in, so that I can optimise the features and UI accordingly. I hypothesise unknown city centres to be one such situation.
What apps do you use to get directions? This could indicate other projects that would be useful to research
What are your main issues with the currently-available apps for routing? Identifying pain points in similar apps will provide ideas for areas to focus on to give my app unique appeal.
Is it more helpful to see a pedestrian route plotted on a map, or a list of directions? To decide how much development time to dedicate to different features, and ensure the result is presented in the most useful way.
What factors should be considered when the program decides which route is best? Gives ideas for which factors should be included into the graph weights, and how much time to spend optimising those factors.
Would a mobile or desktop app be more important for you? I expect that mobile support will be very useful, so that directions can be obtained while out and about. Gauging the importance of a mobile app will determine how much time I might spend on mobile-specific features and optimising the UI for mobile devices.
If the navigation app is used through a web browser, is that a disadvantage or an advantage to you? Although I am almost certainly going to make the front-end using web technologies, it will be useful to know if my users have any complaints or perceived drawbacks regarding web apps, so that I can try and address them.
Is it important for the navigation app to work while you're offline? What situations could you see yourself using this feature in? This will help determine how much of the app should work offline, e.g. whether map data should be downloaded on demand or pre-downloaded. I may use tools like service workers to keep the web app functional when offline.
Initial interview with Andrew

I asked Andrew my research questions and gained useful insight into how pedestrian routing is used in the real world.

Key takeaways
Transcript

In this transcript, Andrew's words are labelled as "AS" and my words are labelled as "MR". I have removed most stuttering, filler words, and interjections that don't add any meaning.

- **MR**: Alright, I'm going to be recording- - **AS**: Hi Mish - **MR**: Hello! Are you alright if I ask you some questions for my project? - **AS**: No. - **MR**: Yes. - **AS**: Yes, I am - **MR**: Which is going to be a project on pedestrian routing, so it will be a navigation app, basically. Okay, I'd like to know first of all, how often you use a app or website to get directions, at all. - **AS**: Probably about once every two weeks, when I'm going somewhere new... how long a journey will take, \[by] car or just walking - **MR**: So you'd say it's especially useful if you're going somewhere new? - **AS**: Yes, definitely - **MR**: Okay. And how often do you use an app for pedestrian navigation? So for just walking - **AS**: I'd say it's about 50/50 with using it for cars, honestly... if I need to just find out how to get somewhere if I don't have a car, which is quite important for me- - **MR**: Yeah, that's fair, yeah. Any situations where you find it especially useful to have that pedestrian routing available? Or is it just in general if you're walking somewhere? - **AS**: Well, yeah, that, but I've found it's also quite useful when I'm trying to find out where someone is, if they give you their location so you can route to that using, Google Maps, usually. - **MR**: Yeah, so have your map coordinates that you can just go to, okay - **AS**: Just checking if it's recording? - **MR**: No, I was just reading my questions. - **MR**: And, what apps do you use or have you used to get directions? - **AS**: Pretty much entirely Google Maps, yeah - **MR**: Sounds good. Do you find its interface intuitive? - **AS**: Yeah- - **MR**: Do you find it, _\[incomprehensible]_ laid out? - **AS**: I have actually used Google maps to find someone before, so there's that. Yeah, it's intuitive, easy. - **MR**: Nice, okay. Anything you don't like about how Google Maps does pedestrian routing? - **AS**: It doesn't have a very good layout of paths, like smaller paths, it just doesn't show, which isn't nice, so I was trying to run to Shere, and I was trying to use the compass to find out which paths to take. - **MR**: Okay, yeah. That's definitely something I'm hoping to improve with this app. - **AS**: Great. - **MR**: So if you're using a navigation app, so you find it more helpful to have a list of directions with road names — "turn on to this road, turn on to that road, cross at this road" — or the route overlaid onto a map, that's highlighted in blue or whatever. - **AS**: Ah, definitely overlaid onto a map. It's quite nice to be able to visualise that. - **MR**: Yep. And how useful is it to have your location on it, so it can be updated live? - **AS**: Yeah, very very useful. Otherwise you're just _\[incomprehensible]_ - **MR**: Mhm, sounds good. And finally, what factors do you think I should consider when deciding which route is best? - **AS**: So when you've got multiple different routes... to get to a place? - **MR**: Yeah, so, which properties or aspects of the paths and roads to consider. Like, obviously, everything else being equal, we'll go for the shortest path, because it's likely to be the quickest, but that's not the only thing that will affect how enjoyable your route will actually be. - **AS**: Oh, okay. That is an interesting comment. - **MR**: Take your time. It's one that requires some thinking. - **AS**: I can only think of really specific things, like if it's been raining, and there's a muddy path, you might want to stick to roads - **MR**: Yeah, that's useful yeah. So, maybe having "avoiding unpaved paths" as an option, as well as just a default thing? - **AS**: And maybe, what, elevation... you don't wanna climb a really steep thing and then go down a really steep thing when you can go around. - **MR**: That's a good point, yeah. That sounds good. - **AS**: I suppose if you could get foot traffic data, but it doesn't really matter if there's a lot of people blocking your path unless there's a lot and a lot of people - **MR**: Yeah, that's good. What about paths being lit at night? - **AS**: Oh yeah, that's a very good point. Yeah, you definitely want to go down lit paths at night. - **MR**: Okay, sounds good! Alright, thanks for answering my questions- - **AS**: No worries. - **MR**: And if you have any other feedback you can email me or tell me. - **AS**: Yep, I probably won't email you. - **MR**: As great as emails are.

Download the full recording (05:16, m4v, 0.5 MB)

Initial interview with James

My initial interview with James was conducted via email. It was very valuable to understand he uses similar navigation apps, and how they compare.

Key takeaways
Desired features
Transcript

Hi Mish,

Sorry for the slow response,

  1. How often do you use an app or website to get directions?

    2 or 3 Times a week at least, I normally use it to plan a route before going.

  2. How often do you use an app or website to get directions for walking?

    Quite often whenever I'm in an area which I don't know that well

  3. In what situations (i.e. what places) are you more likely to use an app for pedestrian navigation?

    I'm most likely to use the app in cities or town which I don't know very well, I also often use a navigation app if I'm a looking for a specific building and I'm not completely sure where it is.

  4. What apps do you use to get directions

    I use a mixture if different apps as they all have there advantages:

    OsmAnd for walking as it provides much better and faster pedestrian routes than its rivals, I also find that the location seems a bit more accurate compared to other apps on this list which is partially helpful when walking.

    Magic Earth for driving but this app uses a lot of battery so it is only really suitable for shorter routes

    Google Maps for planning routes as it shows me all the different modes of transport I can get there. I also often use it to navigate long journeys in a car because it uses much less battery than Magic earth.

  5. What are your main issues with the currently-available apps?

    The OsmAnd UI can be much harder to use at times and it doesn't give you the ability to search along route.

    Magic Earth is primarily a car focus app and therefore regularly give you very inefficient pedestrian routes, It also use too much battery limits how long I can use it for.

    Google maps is also car focused and rarely gives you the most efficient pedestrian route, It also almost never gets the direction you are facing when walking correct which can made following it directions very difficult.

  6. Is it more helpful to see a pedestrian route plotted on a map, or a list of directions?

    I like to be able to see a map, but a list of instructions can be easier to follow and much easier to share with others.

  7. What factors should be considered when the program decides which route is best?

    The speed and distance of the route, how accessible the route is, and the surface of the route depending on the time of year (I probably don't want to walk down a wet and muddy route) the program could give me a warning and offer me an alternative route which avoids these kind if areas.

If you need more details or have any follow up questions let me know,

Thank you,

James

Hi James,

I'd like to ask you a few questions to help research for my pedestrian navigation app:

  1. How often do you use an app or website to get directions?
  2. How often do you use an app or website to get directions for walking?
  3. In what situations (i.e. what places) are you more likely to use an app for pedestrian navigation?
  4. What apps do you use to get directions?
  5. What are your main issues with the currently-available apps?
  6. Is it more helpful to see a pedestrian route plotted on a map, or a list of directions?
  7. What factors should be considered when the program decides which route is best?

If you have any other thoughts or ideas, please share them too.

I look forward to working with you to ensure the navigation app can be as useful as possible.

Mish

Initial interview with Ili

My interview with Ili was done two weeks later than my other two initial stakeholder interviews, so I decided to add a few more questions about the platforms that the app will be available on, in order to back up my plans to make it a cross-platform web app. These questions have been listed and justified at the top of the initial interviews section.

Key takeaways
Desired features
Transcript

In this transcript, Ili's words are labelled as "IR" and my words are labelled as "MR". I have removed most stuttering, filler words, and interjections that don't add any meaning.

- **MR**: Okay, there we are. Bring that a bit closer. Right, first of all, what I'd like to know is how often you use an app or website to get any sort of directions, on foot or by car. - **IR**: I would say, probably 3 times a week. - **MR**: Okay. And how often do you use an app for pedestrian directions? - **IR**: Less frequently, but a couple of times a month maybe. - **MR**: Okay, yeah. And what situations do you use pedestrian navigation in? - **IR**: If I'm in a large city or something, and I need to find a new place I haven't been to before, and I'm not driving, then I'll walk there. - **MR**: Yeah, sounds good. What app do you use for that? For any sort of navigation. - **IR**: Google Maps. The only- - **MR**: Yep, the most common one. Can you think of any issues you have with the currently-available apps — so, Google Maps, basically — for pedestrian routing? - **IR**: I'm not always sure if Google \[Maps] pinpoints the place I want to go to accurately. So you don't know until you get there. - **MR**: Oh okay. Is that like location within a large place, like a shopping centre, or just a specific address where it might not know where you are? - **IR**: A specific address. If it's not a straightforward "Number 5, Acacia Avenue", \[there] can be a margin of uncertainty as to whether its gotten it right or not. - **MR**: Mhm, yeah. If it's 50 or 52 instead of 51 to 53. - **IR**: Yeah. - **MR**: If you're using an app for pedestrian routing, is it more helpful to have a route plotted on a map (like, highlighted on a map) or to get a list of directions? - **IR**: Well I'm quite good with maps, so I prefer a map rather than... directions I find are not so clear, specific, as- - **MR**: Yep. - **IR**: "turn right on a map": I can see where the actual... I prefer a map. - **MR**: Mhm, sounds good. And there are a lot of options for this question, but when the app's calculating a route, it will want to pick the shortest route, but there'll be other factors as well that will influence which route it prefers. Stuff to do with the path or the road that you're on. Are there any aspects that you think would be important to factor in? - **IR**: Yes, so obviously selecting roads that have footpaths on them, rather than a country lane without a footpath, if at all possible. Selecting a route in a busy city centre via pedestrian crossings might be useful, rather than get dual carriageways in the middle of- - **MR**: Yeah, we can definitely do that. - **IR**: ...the middle of Birmingham, for example, and you want to avoid asking people to cross those. You want to go via footbridge or other crossing facilities. - **MR**: Yeah, sounds good. And... I can probably guess the answer to this, but would a mobile or desktop app be more useful for you? - **IR**: Mobile. I don't carry the desktop around. - **MR**: So you can use it when you're actually needing the directions. And if you're accessing the navigation app through a web browser, would that be an advantage or disadvantage to you? - **IR**: To me, it's what I see that counts. I'm not really sure of the technical differences between viewing a picture that's on a web browser or through some other interface, from an app or something. - **MR**: Yep, mhm - **IR**: I mean, if I'm presented with a map I can understand, then it doesn't worry my how it gets there, really - **MR**: Yep. And finally, is it important for you for the navigation app to work while it's offline? - **IR**: That'd be useful, yes. If I had to pick between two apps, and that was the only difference between them, then I'd pick the one that worked offline as well. - **MR**: Yep. - **IR**: One thing that might be useful in a city centre scenario would be a dry route, as opposed to a shortest route. Through a shopping centre, or... - **MR**: So anywhere, sort of, covered? - **IR**: Covered, yeah. - **MR**: Prioritise those places. - **IR**: Yeah. - **MR**: Yeah. - **MR**: Yeah, sounds good. Any specific situations where offline support would be most helpful? Or is it just whenever mobile data is patchy. - **IR**: Yeah, patchy or... - **IR**: Yeah, that's when it's gonna be useful, is when you're in the countryside or something, and the signal's not so common, you might find it useful. - **MR**: Yeah. - **IR**: If you're doing a walk route, which might be across a big hill or something, you might like to have one that works offline. - **MR**: Yeah. Is there anything else you've thought of that you'd want to suggest or mention? Or any questions you have about the project? - **IR**: I don't know whether most mapping apps these days take into account people with colour blindness and suchlike. Was it red and green, or red and blue, that's commonly indistinguishable by people who are colour blind, whether that's something to bear in mind. - **MR**: So, when thinking about how the map's presented, or how it's highlighted. - **IR**: Yeah, the colour of the map. I mean, I'm not colour blind, so I can see things... I don't appreciate, necessarily, that a red route on a green background or something might not stick out very well. So you have that kind of colour blindness. - **MR**: Mhm, yep - **IR**: Apart from that, nothing else spring to mind. - **MR**: Okay, cool. Thank you very much. - **IR**: You're welcome. - **MR**: Hopefully you'll be able to find some use for the app. - **IR**: Yep.

Download the full recording (08:36, m4v, 0.8 MB)

Follow-up discussion with Andrew

On 17 October 2024, I had an informal discussion with Andrew. When I asked him if mobile or desktop support would me more important, he told me that mobile support would be very important. I also asked him about accessing the app through the browser, to which he told me the only disadvantage of that would be the lack of offline access. I mentioned how I could make the web app work offline, which he agreed with.

Similar solutions

As part of my research, I will investigate other programs that provide pedestrian routing. This will include programs that are solely routing engines, as well as map apps that have routing features built in.

OsmAnd (map app)

OsmAnd (osmand.net, w.wiki/BV4b) is a mobile map app that uses OSM data and has routing that runs on-device for a range of transport modes. I have personally found its pedestrian routing to be very good in real-word use, so I will be using it as my primary point of reference to compare my engine's routes with.

Route overlay Directions list Navigation options
A screenshot of the OSMAnd route overlay for walking, highlighted in blue. A screenshot of the directions list for a walking route on OsmAnd A screenshot of the "route parameters" screen in OSMAnd for the walking profile, showing a few options for customising the routing engine
Magic Earth (map app)

Magic Earth (magicearth.com) is a similar mobile map app, suggested by my stakeholder James.

Google Maps (map app)

Google Maps (google.co.uk/maps/about, w.wiki/BV4d) is a popular web app and mobile app.

Route overlay Directions list Navigation options
A screenshot of a walking route in Google Maps. The route is shown as a blue dotted line overlaid onto a map A screenshot of the directions list for a walking route on Google Maps A screenshot of the "trip options" in Google Maps, giving the user two toggles
Valhalla (routing engine)

Valhalla is an open source routing engine and accompanying libraries for use with OpenStreetMap data. Valhalla also includes tools like time+distance matrix computation, isochrones, elevation sampling, map matching and tour optimization (Travelling Salesman).[^valhalla-readme]

[^valhalla-readme]: Valhalla readme file (https://github.com/valhalla/valhalla/blob/3a385045919967a14d5c9cc57610b2111936ac64/README.md), accessed 17 September 2024

Valhalla is written in C++.

Open Source Routing Machine (routing engine)

High performance routing engine written in C++ designed to run on OpenStreetMap data.[^osrm-readme]

[^osrm-readme]: OSRM readme file (https://github.com/Project-OSRM/osrm-backend/blob/203314b1aa5a4cbbd32b8bd47a5c68399bd9d04e/README.md), accessed 19 September 2024

Open Source Routing Machine (OSRM) (project-osrm.org) is a car, bicycle, and pedestrian routing engine with source code available on GitHub (Project-OSRM/osrm-backend).

Algorithm

OSRM either uses contraction hierarchies or multilevel Dijkstra's algorithm, with its documentation recommending to use the multi-level Dijkstra pipeline.[^osrm-pipelines]

[^osrm-pipelines]: OSRM Readme file, "Quick Start" (https://github.com/Project-OSRM/osrm-backend/blob/203314b1aa5a4cbbd32b8bd47a5c68399bd9d04e/README.md#quick-start), accessed 19 September 2024

Experience

Below is an example route that demonstrates two features I like about OSRM: it suggests an equally-valid alternative route (translucent and dotted) as well as the main one (solid), and it gets onto the pavement as soon as possible.

A screenshot of a route overlaid onto a map. The start point is on a road but the route goes onto the pavement to the side of the road at the next crossing

GraphHopper

GraphHopper is a fast and memory-efficient routing engine released under Apache License 2.0.[^graphhopper-readme]

GraphHopper (www.graphhopper.com/open-source) is the third main open-source routing engine that uses OSM data. It's written in Java and supports a range of transport modes, including walking. Its source code is available at https://github.com/graphhopper/graphhopper, and has a useful technical overview document (docs/core/technical.md).

[^graphhopper-readme]: GraphHopper readme file (https://github.com/graphhopper/graphhopper/blob/c0ad6b040b8930ad2a5a28661b211b1289a5d93d/README.md), accessed 9 October 2024

Algorithm

GraphHopper supports Dijkstra's algorithm and the A* algorithm. It also supports contraction hierarchies, which improves speed at the cost of less flexibility to incorporate additional factors (e.g. traffic data).[^graphhopper-technical-overview]

[^graphhopper-technical-overview]: GraphHopper technical overview (https://github.com/graphhopper/graphhopper/blob/c0ad6b040b8930ad2a5a28661b211b1289a5d93d/README.md#technical-overview), accessed 9 October 2024

Project goals and branding

After gaining an idea of exactly what my stakeholders want from a navigation app, I can think about what the high-level goals of the project should be. I will then transform this into some example prose for describing the app, to create a sort of branding that describes what the project will do and what features it will have. I want to capture the "vibe" of the project before I start developing it.

Thinking about branding early on in the project will have a few advantages, e.g. to:

One-line description

I want a one-line description to succinctly capture a few key points of my app:

Brainstorming
  1. "Pedestrian routing for anyone, anywhere"
    • I like how "for anyone" represent the accessibility features
    • "for anyone" could also represent its wide platform support due to running in the browser
    • "pedestrian routing" is perhaps too much of a technical term
    • "anywhere" is intended to represent how you can use it on a mobile device when outdoors, or from your desktop at home. It will also suggest that it supports a wide range of real-world situations. However, the routing engine will be limited geographically to Great Britain, so routing can't actually be done "anywhere"
  2. "Pedestrian navigation, optimised for you"
    • "optimised for you" represents the variety of options that will make it able to cater for a variety of users and situations
    • "pedestrian navigation" is easier to understand than "pedestrian routing"
    • The pronoun in "optimised for you" perhaps sounds a bit vague and overly promotional, where I want it to be mainly descriptive
  3. "Easy pedestrian navigation for anyone"
    • This returns to the "for anyone" phrasing
    • I wanted a nicer synonym for "simple" (as it will be a no-frills app), so I went for "easy"
    • "easy" should also capture the ease of use that I hope to build in to the app by working closely with my stakeholders and holding accessibility as a priority.
  4. "Easy pedestrian navigation for everyone"
    • I changed "anyone" to "everyone" as I feel it elicits an even greater sense of inclusivity and accessibility
  5. "Pedestrian navigation, done right"
    • "done right" signifies the attention to detail that will be put into the routing engine to ensure it uses footpaths, pavements, and other paths correctly
    • "done right" also highlights how the project will improve upon other navigation apps like Google Maps that have inadequate coverage of paths.
    • However, this one lacks the description of benefits to users, like the others have
Conclusion

For users:

Easy pedestrian navigation for everyone

For developers (tentative):

Pedestrian navigation, done right

App name

An overall name for the project (which will also be the app name) will be very important, because it will:

With that said, I don't consider it necessary to decide on an app name at this point, as the app is only being discussed by a small number of stakeholders. It is also likely to be easier to come up with a project name after I've worked on it for a while.

Essential features

Based on my own ideas, initial stakeholder interviews, and research of similar programs, I have produced a list of essential features which will provide the most value to my program's users.

These features are split by features that will need to be implemented on the frontend and the backend. They are listed in order of priority, and designated codes starting from B1 (most important backend feature) and F1 (most important frontend feature). This codes will make the essential features easy to reference later on in the project.

Essential routing engine features

The backend for the project will be the routing engine itself, written in Python.

B1 Route generation

The core utility of a navigation app comes from the route it can generate. It should be able to produce a safe, legal, and fast route between the two provided points.

This is the key functionality of the program, as demonstrated by the fact that all the other features build on top of it: either making it easier to use or adding extra customisability.

B2 API for route requests

The routing engine needs to be accessible from the frontend, so it must have an API that allows programs to request routes to be calculated, and return the results.

B3 Range of options to customise routing

Pedestrians using my app will have varying needs and preferences, so an important feature of the routing engine will be the ability to customise how different paths are weighted to match the user's preferences.

Essential UI features

The user interface (frontend of the project) will run in the browser, and will need a few key features to be a minimum viable product for my stakeholders. Most of these features will depend on a corresponding feature on the backend.

F1 Communication with the routing engine

The frontend will have to send and receive data to/from the routing engine using some form of API. This may be over HTTP, or using some sort of internal communication between the JavaScript and WebAssembly (WASM) runtimes.

This will be essential so that the UI can get the calculated route that so that it can then draw it on the map (as described below).

F2 Drawing the route on a map

My stakeholder interviews, especially with Andrew and Ili, have shown that having the route displayed on a map is often the most valuable way to present the information. This will be done with the Leaflet.js library, by displaying an interactive base map that uses the OpenStreetMap Foundation (OSMF) raster tile server (https://tile.openstreetmap.org/). The route will then be overlaid with a coloured highlight along the paths that make up the route.

F3 Fields to set the available options

The UI should include some form elements that let the user access the different options supported by the routing engine.

The focus should be on providing a good user experience when wanting to plan a route, so not all possible options need to be included, especially those relating to specifics of OSM feature tags. For example, the it may be possible to ask routing engine to prefer paths that are lit at night but not lit 24/7, but this is highly unlikely to be useful in the real world so doesn't need to be catered for in the UI.

F4 Saving options as presets

As discussed above, he UI will include a variety of options, and each user might have their own preferred set of options. They may have a few different preferred sets of options for different situations, e.g. walking at night, jogging, walking for pleasure.

Saving options as "presets" that can be loaded as the start/end locations are being entered, or automatically loaded when the app starts. This will have a number of important advantages:

Forcing the user to enter their preferred options manually would be very undesirable because it would cause the inverse of those advantages.

This should be a feature entirely within the frontend, as the presents just need to be stored individually on each user's device.

While not essential, adding the ability to import and export presets will facilitate sharing them between devices and users, if this is desired.

F5 Accessibility

As a modern web app, it should be expected that the UI will be accessible, working with built-in browser features and accessibility tools to ensure that the UI can be used comfortably, whatever situation the user is in, and whatever accessibility requirements they have.

This is especially important for my routing engine, as part of its target persona is those wanting a routing app that takes into account urban accessibility. For example, a number of routing options (e.g. preferring tactile paving) will bew catered towards those with reduced vision, who may also use a screen reader, or have increased system-wide font size. The UI should accommodate this and work with these tools.

User requirements

Based on the essential features as well as other ideas from stakeholder interviews, I have produced a list of user requirements, i.e. user-facing features that I plan to add to the app. As a user-oriented list, it covers both the frontend and backend of the project. Each requirement has been numbered and justified, and linked to the corresponding essential feature where there is one.

  1. The system should be able to calculate a route between two points (B1)
    • This is the core functionality of the app, as it is what will provide the most value to users
    • This is because that all my stakeholders mentioned that they use navigation apps to get routes between two points
  2. The system should be able to display the route on a map (F2)
    • Both Andrew and Ili mentioned that they prefer to see the route on a map, rather than as a list of directions
    • This will be the most intuitive and user-friendly way to present the route
  3. The system should be able to customise the route based on a range of options (B3)
    • This will allow the user to get a route that is tailored to their specific needs, which will make the app more useful to them
    • I have decided that this will one of the the key areas where my app will stand out from other navigation apps, so it is important to include this feature
    • In addition, my stakeholders James (avoiding wet and muddy routes), Andrew (sticking to lit paths at night), and Ili (sticking to covered paths) have all given examples of routing customisation that can be made available as an option
  4. The system should be able to save routing options as presets (F4)
    • This is an essential companion to the highly-customisable nature of the routing engine, as it will allow users to quickly access their preferred routing options
    • This will make the app more user-friendly, as it will save the user time and effort
  5. The system should be accessible to those with a variety of needs and preferences (F5)
    • Andrew is colour blind, so keeping the visuals of the app within accessibility best practices will ensure he can use it to its fullest extent
    • Ili also mentioned that it is important to consider colour blindness when designing the map, so this will be a key consideration when designing the UI
    • In addition, following accessibility best practices will make the app more usable for everyone, e.g. keeping it usable in bright sunlight (a likely situation for an outdoors-focused app) or allowing for faster data input with a keyboard
  6. The system should function offline, once the necessary data has been downloaded
    • This will make the app more useful to my stakeholders, as it will allow them to use the app in a wider range of situations
    • Andrew told me in his follow-up discussion that offline support would be a very important factor, so ensuring a smooth offline experience will be key to making the app useful to him
    • Ili has also said that offline support would be useful, because you can often find yourself in areas with poor internet access when using a navigation app
  7. The system should be able to import and export routing options presets
    • This is a companion feature to the ability to save presets, as it will allow users to share their presets between devices, or with other users
    • This grants more flexibility to the user, putting them in control of their data, which helps facilitate a sense of openness and trust in the app, as well as making it more user-friendly
  8. The system should perform well and be responsive to a variety of devices, across mobile and desktop
    • All my stakeholders have told me they're most likely to want to use the app on a mobile device, so ensuring it runs well on mobile is key
    • This will dramatically increase the usefulness of the app, as it can be used on the ground for real-time navigation, as well as for planning routes ahead of time on a desktop
    • Testing on a number of different devices will ensure that the app is usable, even on lower-end or unusual devices
    • Ensuring the app adapts to different screen sizes will help it feel like a native app, which will satisfy Ili's statement that it's how the app looks that counts

User requirements signatures

Stakeholder Signature Date
________________________
________________________
________________________
________________________

Limitations of the system

To keep the project manageable and ensure I can focus on producing the features that will be of most value to my stakeholders, I have limited the scope in a few key areas: geographic scope, routing scope, and navigation features.

Geographic limitations

The navigation app will only support start and end locations that are in the United Kingdom, specifically those that are within the United Kingdom region provided by Geofabrik, as specified in the .poly file at https://download.geofabrik.de/europe/united-kingdom.poly.

Advantages of limiting this scope:

Routing feature limitations

While the app will support a number of options to customise the routing graph weights for different pedestrian routing use-cases, the scope of routing features will be limited to those useful for pedestrians (including walking, or using a scooter or wheelchair). Adding support for other modes of transport, like public transport, ferries, cycling, or driving, is out of scope for this project.

Focusing on pedestrian navigation is justified because it has been identified as an important tool for my target persona (as shown in my initial interview with Andrew), as well as being an area where other navigation apps like Google Maps and Magic Earth fall short (as mentioned by James in his initial interview). By filling this gap in the market of available apps, I will be able to achieve the app's goal of making it easier to navigate by foot.

This will help keep the development time of the project manageable, as well as ensuring that the app does its one job well.

Navigation feature limitations

The navigation app will provide a high-quality route and present it to the user. However, most auxiliary features found in other apps, especially Google Maps, are out of scope for the project. This is because these features can be very technically-complex, meaning that they will take a great length of time to research, analyse and develop. Deciding not to implement these features will help the project avoid scope creep, allow me to focus on the core product, should help keep the app performant, and avoid cluttering the UI with features that aren't wanted by my stakeholders.

Some examples of auxiliary navigation features that are out of scope:

There are also some auxiliary features that may be implementable within a reasonable amount of time, so it is possible that they will be added if time allows and they are desired by stakeholders. This includes:

Hardware and software requirements

Most users will access the software through the web app, which only requires a modern browser environment. However, the Python routing engine can also be run separately, in which case it will have its own specific requirements.

Software requirements (routing engine)

[^debian-python-pkg]: See https://packages.debian.org/bookworm/python3 [^python-2-eol]: See https://www.python.org/doc/sunset-python-2/

Hardware requirements (routing engine)

Requirements (web app)

Any other software or hardware requirements will depend on the requirements of the web browser used, so are not included here as they will depend between browser, browser version, and environment.

Design

Program structure diagrams

I have decomposed the main problem into sub-problems, showing the different aspects of the frontend and backend that will need to be implemented. I have considered the essential features list and the user requirements list during this process, and have linked boxes to user requirements (e.g. "UR1") where appropriate.

Overall architecture

A diagram showing the routing engine running within the web app, which runs in a web browser, which interacts with hardware devices

Icons provided by the KDE Breeze icon theme, licenced under LGPL, https://github.com/KDE/breeze-icons

Routing engine structure

graph LR
  A[Routing engine]
  A --> B[Map data]
    B --> BA[Download region]
    B --> BB[Parse OSM tags]
    B --> BC[Compute routing graph]
      BC --> BCA[Nodes and edges]
      BC --> BCB["Weights (UR3)"]
  A --> C["Calculate route (UR1)"]
    C --> CA[Perform A* algorithm]
  A --> D[Communicate with frontend]
    D --> DA[Receive route request]
      DA --> DAA[Start/end location]
      DA --> DAB["Route options (UR3)"]
    D --> DB[Send route data]
    D -.-> DC[HTTP API]
Map data

This subsection contains all the features related to downloading, saving, and processing map data, including creating the graph that will be used to compute the route. I have grouped these tasks together because they are all dealing with the map data, which can then be used by the routing engine to actually compute the route.

Download region

Before the routing graph is computed, the appropriate region of map data will have to be downloaded. Therefore, it makes sense for this to be grouped with the task for computing the routing graph.

Parse OSM tags

OpenStreetMap has its own text-based tag format, which uses plain text attributes to describe properties about map features. I will need to parse the tags that are relevant to the routing engine, so that they can be used to appropriately create the routing graph, set the routing graph weights, and provide additional information to the user after the route is computed, e.g. road names or statistics on surface types.

Since the routing graph will be the primary consumer of OSM tag data, I have grouped this task with the routing graph computation.

Compute routing graph

The routing graph is the data structure that the routing engine will use to calculate routes. It will contain nodes and edges, with each edge representing a path between two nodes. The edges will have weights that represent the cost of traversing that path, which will be used by the A* algorithm to find the best route during the route calculation task.

Route calculation

This subsection contains the task of actually calculating the route between two points, given the routing graph and other parameters to conform to (i.e. types of paths to avoid). The nodes and edges will first be computed, and then weighted based on attributes of the corresponding OSM objects. Those tasks can be done separately to each other so I have placed them as subtasks of this one.

Perform A* algorithm

The route will be calculated using the A* algorithm, so I will need to implement an A* pathfinding algorithm to work on the routing graph. I've added it as a separate box as it is essentially a standalone algorithm that can have its own subprogram.

Communicate with frontend

This subsection contains the tasks related to passing data between the routing engine and the frontend. This will be done using an internal API.

The two subtasks here are receiving a route request from the frontend, and sending the route data back to the frontend. I have separated them out as they will use different data formats and will happen at different times during the route calculation process.

HTTP API

The HTTP API is a potential feature that might be added to allow for more flexibility with using the routing engine in various situations. It will allow the routing engine to be used by other programs, or by the frontend, without needing to be embedded directly into the frontend code. This also means that a HTTP API could be implemented and used if embedding the routing engine is shown to not be feasible during development, ensuring that the project can still be made in some form.

Web app structure

graph LR
  A[Web app]
  A --> B[Accept input]
    B --> BA[Start/end location]
    B --> BB[Route options]
  A --> C[Communicate with routing engine]
    C --> CA[Request a route calculation]
    C --> CB[Receive route data]
  A --> D["Display interactive map (UR3)"]
    D --> DA[Base map]
    D --> DB[Highlight route on map]
    D --> DC[Current location dot]
  A --> E["Manage presets (UR4)"]
    E --> EA[Save presets]
    E --> EB[Load presets]
    E --> EC["Import/export presets (UR7)"]
  A --> F["Offline support (UR6)"]
    F --> FA[Use service worker for caching]
    F --> FB[Allow pre-downloading map data]
Accept input

This will likely be the first thing the user looks to do when they open the web app and see the UI, so I have listed it first. This will primarily mean selecting the start and end locations, but route options will be input in a similar way and at the same time, so they are grouped in here.

Communicate with routing engine

This is the part that will prompt the routing engine to calculate a route, which is naturally quite an important part of the frontend. It corresponds to the communicate with frontend task of the routing engine, and they have similar sub-tasks: communicating the route request information, and receiving the route data.

Display interactive map

An interactive map is user requirement 3 for the project, so it is important that it is implemented.

Base map

The base map will provide important context of where the route is, what roads and paths are in that area, and what paths are being followed. The base map is also useful for orienting the user to make it easier for them to follow the route.

Highlight route on map

After the route has been calculated, it should be highlighted on the map, as this is the most intuitive way to present the route to the user. I will use Leaflet.js's features to accomplish this.

Manage presets

Presets make the wide number of options more manageable to work with, as well as allowing transferring of options between devices, making the app more useful.

Saving and loading presets are the two actions that any preset feature will need to have implemented, so those are the first two sub-tasks (corresponding to user requirement 4).

The other sub-task is importing and exporting presets, which allows working with presets in more ways (as per user requirement 7).

Offline support

Offline support is user requirement 6, and implementing it will require both the app's code (managed by a service worker) and the map data to be stored locally.

Technology decisions

Frontend technologies

Thingy Technology to use
Programming language Typescript
Other languages HTML, CSS
Build tool Vite
Package manager Yarn
Python interpreter Undecided
UI library daisyUI
TypeScript

TypeScript (typescriptlang.org) is a superset of JavaScript designed to improve developer experience by adding a type system to catch type errors while writing code. I have chosen it for a number of reasons:

[^stack-overflow-survey-admired-languages]: Most-admired programming, scripting, and markup languages, Stack Overflow Developer Survey 2023 (https://survey.stackoverflow.co/2023/#programming-scripting-and-markup-languages)

Vite

Vite (vite.dev) is a build tool for JavaScript and TypeScript code, which will handle compiling my TypeScript code to JavaScript, as well as including my dependencies. I have picked it for the following reasons:

Yarn

Yarn is a package manager for JavaScript/TypeScript, which will mean that it can help me use any Javascript libraries I'll need in my project. The reasons I've chosen it are similar to my other technology decisions:

daisyUI

daisyUI (daisyui.com) is a UI library for web development. It will provide ready-made styles for components like buttons, dropdowns, and switches, which should greatly help with developing the frontend because I won't have to reinvent the wheel with my own styles for very element I need. While I haven't used it before, I have used the tool that it's built on top of (Tailwind CSS) so it should be easy for me to install and start using it. Other advantages are:

After creating mockups of parts of the app using daisyUI, and showing them as well as the official demos to my stakeholders, I've decided to stick with daisyUI for the project.

Python interpreter (undecided)

I will decide what technique and library to use for running Python code in the browser during the design part of Sprint 2, as written in my Sprint 2 upfront plan.

Stakeholder discussions about daisyUI

I showed Andrew a demo of daisyUI and he liked the different components available, saying that they seemed easy to use.

Data structure research

Bad programmers worry about the code. Good programmers worry about data structures and their relationships. — Linus Torvalds

Routing graph research

The routing graph is the most important data structure to get right in the program, as almost every part of the routing engine will use it.

It has the following requirements:

  1. Nodes and edges that I can attach extra data to, perhaps through object references

  2. Weights on edges and nodes

  3. Ability to transverse the edges in either direction

    • This could be implemented either by having two edges for each path, or by having a single edge that can be traversed in either direction
    • Even if one-way roads are best represented as directed edges, it is very uncommon for one-way restrictions to apply to pedestrians in the UK

  4. Decent performance for creating the graph

    • The graph will only be computed once for a certain region

  5. Great performance for traversing the graph

    • The graph will need to be widely traversed during route calculation, which may also happen multiple times if the user adjusts a route slightly
Deciding between an undirected or directed graph

It may be desirable for routing graphs to be directed for a number of reasons. I will consider them, as well as considering the extent to which they apply to my project.

I have not tested or researched the differences in performance between undirected and directed graphs, but I don't expect a directed graph to be drastically faster than an undirected graph.

The main advantage of an undirected graph is its simplicity: in a similar way to how each graph node will have a 1:1 relationship with a OSM node, each edge will have a 1:1 relationship with a specific segment of an OSM way. This should make it easier to implement, and easier to calculate edge weights, as a corresponding OSM way will always be present.

Explanatory diagrams for the routing graph
How graph nodes/edges relate to OSM elements
erDiagram
  "OSM way" 1+--1 "Graph edge" : "links to"
  "OSM way" 1--1+ "OSM node" : "has"
  "OSM node" 1--1 "Graph node" : "links to"
Investigating the routing graph in Routor

A valuable program to investigate at this point is Routor, a routing engine for OpenStreetMap that is also written in Python (github.com/routeco/routor, routor/engine.py). It uses the NetworkX library to implement a directed graph.

Routor, as a general-purpose OSM routing engine, uses a directed graph (networkx.DiGraph) to implement its routing graph. However, I plan to use a undirected graph (networkx.Graph) instead, as discussed under deciding between an undirected or directed graph.

Investigating the suitability of NetworkX

NetworkX (networkx.org) is a Python library that implements various graph data structures and algorithms. I looked for a library that implemented a graph data structure for a couple of reasons:

NetworkX would be a good choice for the following reasons:

While NetworkX implements shortest path algorithms, including A*, I still plan to implement my own A* algorithm. This will:

Routing graph research conclusion

With this research in mind, I plan to use the NetworkX library to store and interface with the routing graph in-memory, using the networkx.Graph class to implement an undirected graph.

Class diagrams

Class diagrams for OSM data

classDiagram
direction TB
class Coordinates {
  +lat: float
  +lon: float
}

BoundingBox "1" *-- "2" Coordinates
class BoundingBox {
  +min_lat: float
  +min_lon: float
  +max_lat: float
  +max_lon: float
  +contains(point: Coordinates): bool
  +top_left(): Coordinates
  +bottom_right(): Coordinates
}

class OSMTag {
  -key: str
  -value: str
  +text(): str
  +is_truthy(): bool
  +is_falsy(): bool
}

OSMElement "1" *-- "*" OSMTag : tags
class OSMElement {
  <<abstract>>
  +type: str
  +tags: dict[str, OSMTag]
}

OSMNode --|> OSMElement
OSMNode "1" *-- "1" Coordinates
class OSMNode {
  +pos: Coordinates
}

OSMWay --|> OSMElement
OSMWay "1" o-- "n" OSMNode : nodes
class OSMWay {
  +nodes: list[OSMNode]
}

OSMRelationMember "n" *-- "1" OSMRelation : members
class OSMRelationMember {
  +role: str
  +element: OSMElement
}

OSMRelation --|> OSMElement
class OSMRelation {
  +members: list[OSMRelationMember]
}

%% OSMRegion "1" o-- "*" OSMElement : nodes, ways, relations
OSMRegion "1" *-- "*" OSMNode : nodes
OSMRegion "1" *-- "*" OSMWay : ways
OSMRegion "1" *-- "*" OSMRelation : relations
OSMRegion o-- BoundingBox : bbox
class OSMRegion {
  +nodes: dict[int, OSMNode]
  +ways: dict[int, OSMWay]
  +relations: dict[int, OSMRelation]
  +bbox: BoundingBox
}

Class diagrams for routing

---
  config:
    class:
      hideEmptyMembersBox: true
---
classDiagram
direction BT
RouteResult "1" *-- "n" RoutePart : parts
class RouteResult {
  +start: Coordinates
  +end: Coordinates
  +parts: list[RoutePart]
  +distance(): float
  +estimated_time(): float
}

class RoutePart {
  <<abstract>>
}

%% FIXME Spelling?!
RouteManoeuvre --|> RoutePart
class RouteManoeuvre {
  <<abstract>>
  +estimated_time: float
  +description(): str
}

ChangePath --|> RouteManoeuvre
note for ChangePath "Going/turning from one path to another"
CrossRoad --|> RouteManoeuvre
class CrossRoad {
  +crossing_node: OSMNode
}
StartWalking --|> RouteManoeuvre
note for StartWalking "The first part of every route"
Arrive --|> RouteManoeuvre
note for Arrive "The last part of every route"

%% TODO more RouteManoeuvres?

RouteProgression --|> RoutePart
class RouteProgression {
  +distance: float
  +estimated_time: float
  +along: OSMWay
  +description(): str
}
classDiagram
direction TB
class RoutingGraph {
  -graph: networkx.Graph
  -osm_data: OSMData
}

class RoutingOptions
%% TODO RoutingOptions

RouteCalculator *-- RoutingOptions : options
RouteCalculator *-- RoutingGraph : graph
class RouteCalculator {
  -graph: RoutingGraph
  -options: RoutingOptions
  +calculate_route(start: Coordinates, end: Coordinates): RouteResult
}
note for RouteCalculator "Contains all the state/data required for one route calculation request"

class RoutingEngine {
  %% TODO: How on earth is the compute_graph() function meant to actually work
  +compute_graph(map_data: OSMData): RoutingGraph
  +calculate_route(start: Coordinates, end: Coordinates, options: RoutingOptions): RouteResult
}

Inputs and outputs

Inputs

UI mockups

Some of my mockups were made in Figma, and interactive versions can be accessed online: https://www.figma.com/design/jbFmOUqG90DkDqRnpOlqAF/Routing-app-UI-mockups.

UI component mockups

Combination button

This would be used to select a preference for a certain routing option, like whether to avoid or prefer a certain type of path.

Combination button (iteration 1)

This button was made with Excalidraw.

A combination button, showing "avoid", neutral, and "prefer" states

Andrew's feedback:

Combination button (iteration 2)

I used Figma to make this mockup, so that the rounded corners could be neater.

A neater combination button, showing "avoid", neutral, and "prefer" states

Combination button (iteration 3)

I need to add a way to show which option is selected and which can be pressed. This should be intuitive to make the app easy to use.

Combination buttons showing the "neutral" state selected

Combination button (iteration 4)

I decided it'd be helpful to create a UI mockup using daisyUI, the component library that I'll be using.

A browser mockup of combination buttons

Combination button (iteration 5)

Combination buttons with inset shadows to show selected state

Sprint planning

gantt
  title Sprint schedule
  dateFormat YYYY-MM-DD
  axisFormat %b %d
  tickInterval 1week
  section Schedule
    Analysis phase: 2024-09-04, 2024-10-10
    Design phase: 2024-10-10, 2024-11-12
    Sprint 1: 2024-11-12, 2024-12-05
  section Actual
    Analysis phase: 2024-09-04, 2024-10-10
    Design phase: 2024-10-10, 2024-11-15
    Sprint 1: 2024-11-15
%% TODO what do we do with this
gantt
  title Sprint timeline (test)
  dateFormat X
  axisFormat Sprint %s
  tickInterval 1second
  section Frontend
    %% Final milestone : milestone, m2, 2024-11-30, 4m
    Task 1: 1, 2
  section Backend
    Task 2: 1, 2
    Task 3: 2, 3

Sprint 1 upfront plan

Sprint 2 upfront plan

Sprint 3 upfront plan

Sprint 4 upfront plan

Sprint 5 upfront plan

Sprint 5 will be added if required, and will be planned in more detail once the results of the previous sprints are known. I may use it to work on improving the frontend to ensure it works offline, has a good mobile experience, etc.