Wow :D you really had the patience to put up all those walls. Good thing I used Svelte for the project and made the rendering as smooth as possible :P

Yup, I based this app on that article as matter of fact!

Its due to this: https://github.com/ssaric/algoviz/blob/012c60acb2fa452ee5a3c... Currently heuristics is hardcoded to be greedy. I am looking to change this in next few days

Just remove the "100 *" and it should be optimal.

Thanks! I will keep app as a reference for my future feature development. The app will lean towards understanding the algorithms rather than being used in other apps.

Good idea, I'll add it to the roadmap. Thanks!

Hi, I made this little app to better understand how A* works. I decided to continue developing it for educational purposes.

Computation is done on worker so main thread should be safe all the time.

I plan to add textual information on each step, to show how algorithm is "thinking".

Also, heuristics is fixed for now, I plan to add heuristics choice. So,

Roadmap: - different heuristics - 8 way support - Detailed explanation of each step

Let me know what you think!

I believe A* should always give the minimum path as long the heuristic is optimistic. It will become a greedy search if the heuristic is pessimistic. If the heuristic is "perfect" i.e heuristic(x to y) = min_cost(x to y) the the search will be optimal (i.e no nodes that do not belong with the path will be explored)

Yep after playing around with it for a bit it didn't give a minimum path. I believe something is wrong with the heuristic you are using.

Edit: You can prove A* will give a min path as long as: heuristic(x to y) <= min_cost(x to y). Problem seems to be here https://github.com/ssaric/algoviz/blob/master/src/util/GridN... I think it should be a matter of removing "times 100"

I believe the push and pull is between optimal path and time to find the path. The heuristic dictates whether the algorithm will lean towards Dijkstra or Greedy or somewhere in between.

I got my knowledge about heuristics from here:

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics...

Whether a greedy heuristic is faster or not is dependent on the structure of the graph. For the example in the article about mountains and grassland, it makes sense that such a heuristic would speed up the search, since the algorithm can't get stuck in dead-ends.

But in a problem where the algorithm can get stuck in dead-ends, it's possible to construct examples where the greedy heuristic is (much) slower than plain Manhattan distance. Here's an example:

                xxx
                xEx
                x x
                x x
                x x
                x x
  Sxxxxxxxxxxxxxx x
                  x
   xxxxxxxxxxxxxxxx

Nice visualization!

I don’t think the algorithm is correct though. The heuristic seems to use Euclidean distance instead of “how the crow flies” and thus this implementation goes along the axis instead of directly towards the goal. This causes the algorithm to find the optimal route only occasionally and probably has little to no effect on average execution time.

I just realized my terminology was way wrong. Sorry.

You have Manhattan distance and you want Euclidean distance to make sure the path is always optimal. Execution speed should be the same or better in the average case with Euclidean distance.

One interesting heuristic is h(x) = 0, which is also [admissible](https://en.wikipedia.org/wiki/Admissible_heuristic) and transforms your A* into an uninformed heuristic as far as I remember.

In this case, wouldn't it be shorter to go down first, then to the right? What's happening here?

https://imgur.com/a/xfAtkML

A* is not guaranteed to find the optimal route - it depends on the heuristic and the environment.

Very cool. Definitely curious to see this part:

> I plan to add textual information on each step, to show how algorithm is "thinking"

I've set up the app in a way that I am sending "steps" from the worker. That way I can describe each step textually. I'll post updates here probably!

Personally, I don't mind the concept. I can write CSS on a microwave if I have to. But CSS is supposed to be simple, not to be mixed with JS.

There are good designers out there who know HTML and CSS but not JS. This will lead to a problem for those people.

Let's be honest, you cannot just jump into a React component and edit CSS if your knowledge of JS is slim to none.

There are good designers out there who don't know HTML, CSS or JS. There are also good designers out there who know all three.

CSS-in-JS (or if not, BEM at the least) is a closer fit to the mental model of styling things in design software like Sketch and Figma. So having to use CSS in full utilising-the-cascade-and-complex-selectors mode could reasonably be seen as a bigger barrier to entry than just using something like Styled Components or Emotion. I've come across plenty of designers comfortable with CSS who felt more at home using Styled Components.

I'm not arguing that there won't be some people for whom CSS-in-JS creates barriers, but there will also be others for whom it knocks them down.

Scoping. The way you style a large, complex application is going to be very different using CSS-In-JS vs pure CSS.

I think you're missing the point you can do both? If you want to load a global stylesheet for common theming and then provide component level CSS in JS then that's absolutely fine and even suggested. Having dealt with many styling solutions in my time I find using styled components with the style mentioned is one of the greatest developer experiences I've had in many years. Being able to interpolate your react state within your css is just great and opens up the doors to massively simplify dynamic layouts which the state of which are much better represented in JS

Yes, it is going to be safer and much simpler.

I don’t understand, simple things do tend to be reliable.

yes

Thanks for sharing this amazing experience with us ^_^