Doing any math with bounded integers considered harmful.
At some point during my undergrad I realized this and tried to be really careful when implementing algorithms, but it's stupidly hard to do in a tidy way, at least in old C. It's not practical and people just rather close their eyes and live in blissful avoidance.
It'll keep popping up because it's not practical to have a fully fledged database system running if your data can be downloaded in a few seconds with a phone on a decent 5G network.
DHH and friends have recently been evangelizing it like there’s no tomorrow. Simon Willison has been bullish on SQLite for the last six years.
The Go community is pushing out tools like Litestream and LiteFS. Plus, people at fly.io, especially Ben Johnson, are heavily proselytizing SQLite. All of this adds up. Being a fantastic piece of software in its own right also helps.
This is the only annoyance with UUIDs, I won't be typing it because its 5 characters shorter. Separators are nice because I can try to visually compare Ids, but it needs to be a visual separator that won't break a `word`/`WORD` (whatever boundary that is by default on most terminals and browsers) select by double clicking.
I want to just double click and copy, dragging is annoying.
TBF when dealing with I/O using the right async constructs is way more important than the choice of programming language, I/O times will dominate and any mistake on the wrong wait will ruin performance.
Absolutely but "blazing fast" has become kind of a meme among rust projects. Getting a bit tired of seeing it everywhere personally, at least show me some benchmarks when you make claims like this.
No shade against this project (or rust in general) though, it looks very nice and I wanna try it out.
Yes, but not too long ago they ruined the Android app and made it depend on their servers. At least the watch works fine, but I suspect it's only because the battery isn't large enough to cut lazy devs and hasty PMs from working on harder problems.
I feel this is not needed if you tie-break nodes in Open to favour lower h-values. This leads to a node selection bias for deeper paths, which are more likely closer to the goal.
If you look at runs, this tie breaking makes A* behave like a greedy algorithm in the absence of obstacles and simply follow a straight path if there's one, and act sort of cleverly when there's a small detour.
On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths.
The idea goes: Best to just search in that space vs iterating over some other space attempting to indirectly coax out the optimal path. The bonus is that VG-based search is very fast b/c it doesn't search over anything but those. It's just everyone already has grids so they probably just would rather use that.
That's all I'm claiming. That, and TFA is basically the same as VG-based search. So, yeah, there are infinite ways to find paths, some optimal some not, some doing more work, some doing less. They'll all probably be fine but not all come with books of guarantees. OP has done a good job to intuit an optimal algorithm with fantastic performance guarantees in this setting.
> On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths.
You would still be choosing a node with the best f-value, so you'll get optimal solutions with any admissible heuristic. In a 2D-grid your heuristic should also be consistent, which will result in pretty good behaviour.
- Run A* on the optimistic pathfinding graph (no obstacles on the unknown cells).
- Follow the path found (if there's none, that's it)
- As you follow the path, sense the world and take note of new obstacles.
- If there's an action you can't make because of a new obstacle, re-run A.
There's ways of re-using the state from previous A runs (as long as the goal is still the same) that becomes handy on complex maps where the path you wanted to follow is blocked deeply.
BTW, if you tie-break nodes on lower heuristic value (h-value), then you'll be more likely to search deeper paths, which makes optimizations like trying to follow a straight line kind of useless, but as always, run benchmarks before guessing.
Also, if you have a tight deadlines for the search algorithm, like having to make another tick on the game happen, there's some real-time variants of A* that have a bound for how many nodes A* can expand on each run.
I don't think you'll need real-time A* though, I remember that this approach using Dijkstra was fast enough for a project back in Uni on now 15yo hardware, so newer hardware using A* must be good enough ever for large graphs.
As far as I’ve researched, if there’s an assumption that there are no obstacles, the fastest way to select a straight path is Bresenham's Line Algorithm.
If I’m mistaken about this, please let me know!
In my project, since I don’t need to guarantee complete real-time processing, there isn’t an absolute necessity to find paths as quickly as possible.
However, since many entities need to find paths simultaneously, I’d like to keep the computations as minimal as possible.
It might be similar to what you mentioned about algorithms being fast enough on low-spec hardware.
In my case, I’m currently using an ultra-low-power Mini PC with an *N100 CPU* as a server.
This choice not only helps me study methods to optimize performance but also satisfies my curiosity about fully leveraging the advantages of *MSA (Microservice Architecture)*-based services.
A* searches on a generic weighted graph, there's no vertical, horizontal nor diagonal movements. The only thing that matters is which nodes exists and how they are connected.
If diagonals on a 2D-grid are forbidden, then you need to use the Manhattan distance as the heuristic.
I don't think it's just the carbs, but they likely don't help in today's society. We became too efficient at packing carbs in our diet and at the same time too sedentary.
Beyond macro-nutrients, what I think the true reason food in the US is bad is because of the other stuff. Many things banned in Europe (which is special because they use science for improving quality of life before profits) are not banned in the US, even though it's an advanced enough nation to be able to deal with the ban and look for better options.
The problem in the US is that profits are of utmost importance. Anything that lowers your costs is good for business as long as it's hard to point at it (does colourant X cause cancer? maybe we need more studies, or just didn't know, we'll try better next time).
At some point during my undergrad I realized this and tried to be really careful when implementing algorithms, but it's stupidly hard to do in a tidy way, at least in old C. It's not practical and people just rather close their eyes and live in blissful avoidance.
reply