I’ve been using graph theory for years professionally. A good example of practical uses of graph theory is any routing software. It is basically graphs all the way down.
For starters the whole street network is represented as a directed graph. The most widely used algorithm is the venerable A* to find paths through the vertices of the graph, not necessarily the shortest distance but the most optimal distance given all the trade-offs you wish based on the heuristics you define. There are lots of variations of A* and today most implementations would use its faster cousin: bidirectional A* which attacks the point-to-point calculation from both ends at the same time.
Then you have Dijkstra which is used for flood searches to e.g. give the best cost back home from every vertex so you know when to turn back the search if you have a search budget.
Menger’s theorem I’ve used in order to determine whether we can create a loop back. Basically search outwards, then search back without visiting those same edges.
Tarjan to ensure we identify all subnetworks so we don’t get stuck in a disconnected island of vertices with no way out to join the wider network.
A lot of these algorithms were conceived decades ago and are still the backbone of modern routing software.
One thing that’s constantly been in the back of my mind is, since routing is a highly deterministic problem space, it doesn't seem plausible that LLMs can take this over. It seems to me that it's a good example of a tool that LLMs would call out to rather than implement themselves.
In fact, see this convo I had with @simonw wherein he had Astra generate a jogging route. It setup a whole GIS stack and took about half an hour. That seems like a boil the ocean kind of approach and I’m not sure if that’s ever going to be optimal. https://x.com/baz_shkara/status/2099118620647305630
> seems like a boil the ocean kind of approach and I’m not sure if that’s ever going to be optimal
Finding the most optimal traveling salesman problem for 20 cities by brute force will take a few universes lifetimes and you still won’t be halls way. You’ll need to compromise with heuristics but that usually leads to near optimal
Although the simplest exact algorithm for TSP is O(n!), you can use dynamic programming to get the difficulty down to O(n^2 * 2^n), which is quite tractable at n=20.
However, sometimes you can construct exact solutions to much larger real-world data sets (tens of thousands of points) by exploiting structure in those graphs.
Gamifying the map definitely helps to pull in contributors. StreetComplete got me editing more than anything else. I went a bit sideways with it: I used OSM data to build a territory game for cyclists, where you claim roads by riding them.
It's heavily processed OSM data with PostGIS. The fun part was figuring out how to decide what counts as a claimable road in the first place.
Hey HN, excited to show you something I've been working on for a couple of years. I'm a passionate road cyclist and a former fruit company engineer. Today, there are two primary ways of knowing where to ride your bike: user-uploaded GPX files and generating routes via heatmap data. Both seemed inadequate to me after I was burnt countless times by being sent down high-speed roads or farm tracks.
When I want to go for a ride I have a specific time window in mind, and my goal is to get out and see nature and experience that unique feeling of freedom and joy that comes from riding a bike. So I built the tool of my dreams.
Remap reads the traffic levels, max speeds and road surface quality around you, then calibrates what road comfort means for your area. This leads to users getting comfortable routes out of the box automatically. Plenty of options are also available since cycling is a very opinionated sport.
The other important aspect of Remap is that it identifies what I've been calling 'lines' - sections of road that are excellent for cycling. Broadly speaking they need to be long, surrounded by nature and be away from traffic.
A great ride is full of lines, no ride is perfect end to end, but the more lines a ride has the better it feels. The other part of a great ride is that it should let you explore as wide as possible around where you start from, hit nature as much as possible, give you a climb here and there if you want, and not repeat any roads coming back - so it should ideally be a broad loop. Trying to fit all of this into an unpredictable road network with road rules and a set target distance alongside a large list of user-customisable routing preferences is a tall order, but I've succeeded in building something I'm immensely happy with, and I've been riding all summer with routes generated by Remap. It's been banger after banger ride.
Under the hood, it's a shared Rust core between web and iOS. Probably the most interesting part is route generation occurs locally on-device. I made this decision early on since I knew that this would be very expensive in terms of compute. The routing graph is a highly compressed columnar db that is able to be streamed directly to devices or browsers and be stitched across boundaries to provide a complete road graph. Routing tiles are fetched in Hilbert order so that multiple tiles in the same vicinity can be coalesced together. The architecture was inspired by Brandon Liu's pmtiles project which I'm a big fan of.
After the client has assembled its slice of the graph, it then explores it extensively. Much more deeply than traditional server-based routing software allows, since we have much more compute available we can examine all the side streets and roads that are relevant for delivering optimal bike routes. Using contraction hierarchies or some other optimisation designed for car navigation would defeat the purpose as bikes don't drop into arterials and then back out again like cars do.
The final point of Remap is that it makes solo riding social. You can't always schedule a group ride easily and whilst it's nice to ride solo, I often miss that social element. Since every ride built strings together lines, those lines are valuable and can be owned and claimed by players. The more you ride, the more 'watts' you earn to defend your lines.
I've got a full-time fuzzer going which hits up different cities and generates routes trying to catch out dive-bombs (unnecessary short detours), spurs (pointless out and back sections), various other anomolies. It's been running for a few weeks and caught some good bugs, but I'm really looking for real-world use right now. It's free to use, has a desktop and mobile site, as well as native iOS app. The native iOS app is fastest at route generation but the WASM isn't that far behind. Give it a go and let me know how you fare. Thanks HN!
Pretty sure VRC uses curl under the hood to perform all requests. It’s great being able to use plain text within Vim to formulate and reuse API calls right next to your code.
GitHub isn't a 'single point of failure' due to the distributed nature of Git. I.e. it's pretty easy to push your codebase to another server anytime you want.
If this service backs up submodules for 3rd party dependancies this might be useful but as it stands the landing page doesn't give any further information. I don't feel incentivised to login with GitHub OAuth.
Sorry to hear about this, but don't let it dishearten you from making games and open sourcing them.
Someone stealing your code doesn't take away from the fact that you accomplished your goal of making a complete game. And from what you just wrote - that was your intention.
Regarding your blog title, I'd add 'timing' as well as 'marketing'. Titles of both submissions were remarkably similar ("Flappy Bird in HTML5" vs "Flappy Birdy html5 clone created using the Phaser framework"). Maybe the timing of your submission was off.
Also you can now state that you're the original creator of all the HTML5 Flappy Bird clones that have been popping up recently.
I was ecstatic to see the other forks but my smile does a 360 everytime I see him getting the credit for it. But I'm happy to report that it didn't discourage me to open source the things I create: https://github.com/marksteve/val :)
Yeah. My timing was off. But I think I now have a better idea on when and how to post things here :P
I can't claim that :P There are some good clones that were genuinely created from scratch like mine.
I used to be in that situation which is why I wrote Bee (http://neat.io/bee/). Its a Mac client for JIRA (amongst other services) and makes JIRA much more pleasant to use.
JIRA's UI tends to be geared towards project management types. I wanted to bring the focus back onto the engineer.
However, Jira fundamentally is about managers tracking work, and not about workers actually getting stuff done. There's no way I can track all my tasks in Jira even if I have a nicer GUI for it.
I'm actually part of the way towards writing a program to sync tasks between Asana and Jira using their APIs. I'm hoping that that'll let me continue working in Asana while it handles Jira (which I've always found incomprehensible) for me.
Well you'd be surprised. I've also tried to solve this problem.
You can create your own lists inside of Bee which filter issues based on your own rules (http://neat.io/bee/docs/smart-lists.html). It's helpful because you just define the rules one-time and then flick to it whenever you need to.
Bee also has a menubar helper which tracks your short-term tasks and queues up your next issue so you always know what you're working on (http://neat.io/bee/docs/the-short-list.html).
Also you can add your own Notes list which is just a series of text files (easily synced via Dropbox) if you want to track your own local tasks.
I'm constantly iterating based on user feedback so if you have time, please let me know how it works out for you :)
I just wanted to chime in and say I like your approach of just focusing on pull requests. There's another app I know of that just focuses on creating issues (http://issuepostapp.com).
For starters the whole street network is represented as a directed graph. The most widely used algorithm is the venerable A* to find paths through the vertices of the graph, not necessarily the shortest distance but the most optimal distance given all the trade-offs you wish based on the heuristics you define. There are lots of variations of A* and today most implementations would use its faster cousin: bidirectional A* which attacks the point-to-point calculation from both ends at the same time.
Then you have Dijkstra which is used for flood searches to e.g. give the best cost back home from every vertex so you know when to turn back the search if you have a search budget.
Menger’s theorem I’ve used in order to determine whether we can create a loop back. Basically search outwards, then search back without visiting those same edges.
Tarjan to ensure we identify all subnetworks so we don’t get stuck in a disconnected island of vertices with no way out to join the wider network.
A lot of these algorithms were conceived decades ago and are still the backbone of modern routing software.
One thing that’s constantly been in the back of my mind is, since routing is a highly deterministic problem space, it doesn't seem plausible that LLMs can take this over. It seems to me that it's a good example of a tool that LLMs would call out to rather than implement themselves.
In fact, see this convo I had with @simonw wherein he had Astra generate a jogging route. It setup a whole GIS stack and took about half an hour. That seems like a boil the ocean kind of approach and I’m not sure if that’s ever going to be optimal. https://x.com/baz_shkara/status/2099118620647305630