HNHacker News
TopNewBestAskShowJobs

amitp

930 karma · joined January 14, 2012

I try to write better explanations of algorithms. I'm in the Silicon Valley area (south bay) and am happy to meet for coffee or lunch. See my interactive tutorials at https://www.redblobgames.com/

twitter:@redblobgames

submissionscomments
amitp··on Solving puzzles faster than humanly possible
I'm happy with Steam on Windows but hate its behavior on Mac. It's slow and keeps stealing focus while starting up. I haven't gotten the "choose user" thing though. Cmd-Q does quit Steam for me.
amitp··on A Cursory Look at Cursors
I use a solid box in a terminal and for coding, and a vertical bar for writing in emacs org-mode. But I recently tried out a one-third box[1] in emacs and I am really loving it! It's partway between a box and an underline. Some software has a half-box option but I don't think MacOS Terminal or iTerm2 have that. [Edit: I was wrong — iTerm2 has an advanced setting for "underline cursor width"]

I used to use flashing but have that turned off right now, for reasons I can't remember.

[1] (setq-local cursor-type '(hbar . 8))

amitp··on Flow Field Pathfinding
Thanks! I'll add a note about that.
amitp··on Flow Field Pathfinding
You're welcome! I try to keep the pages fast loading with minimal dependencies but have varying success depending on the needs of each page.
amitp··on Flow Field Pathfinding
That's great to hear! Thanks!
amitp··on Flow Field Pathfinding
Thanks! Yes, I've been making interactive diagrams for a long time. I wrote about my motivation in 2007 [1]. In the early 2000s it was Java applets, and then I switched to Flash applets, and then HTML5 in 2011. That was also around the time I ran out of disk space on my stanford site (they give me 100MB) so I bought a domain name, redblobgames.com. That was also around the time there was enough cross-browser support for me to switch to HTML5. And then in 2014 Bret Victor wrote about "explorable explanations" — that's when I felt like I wasn't alone in wanting this type of thing.

[1] https://simblob.blogspot.com/2007/07/interactive-illustratio...

amitp··on Flow Field Pathfinding
Author here. A surprise seeing this on HN!

The context: I'm writing my own blog software for various reasons [1], including my desire to post less to social media. As much as possible I'm trying to reuse the build system for the rest of the site, including the template. I have worked on and off on this for the past two months and I expect to keep adding features for another month or two. I'm currently adding categories not only for the blog but to the whole site. After that I'll work on archives by month. And I want to import the 21 years of old blog content [2] which is stored on blogger.com, and put it on the new blog, which is just a folder [3] on my existing site.

I'm writing some blog posts to test out the workflow (integrating into emacs, my build script, an internal status page) and also various content types (images, video, source code, figures, links). Each time I post I find some more things to tweak.

This post to HN made me realize that it's not labeled as a blog post. Oops. I guess that's one of the downsides of reusing the exact same template! So another tweak coming…

[1] https://www.redblobgames.com/blog/2024-03-08-new-blog/

[2] https://simblob.blogspot.com/

[3] https://www.redblobgames.com/blog/

amitp··on Geoengineering test launched in Alameda
This is called "moral hazard", and it is something to consider. Yes, moral hazard is a danger, but doing nothing is also a danger.

https://www.sciencedirect.com/science/article/abs/pii/S22146...

amitp··on A* tricks for videogame path finding
There are lots of variants of A* that depend on what you can assume about your graph, whether you can preprocess, how often the graph changes, etc. Contraction hierarchies, subgoals, bidirectional A*, hierarchical search, all-pairs compression, moving obstacles, group movement, coordinated movement, landmarks, labeling algorithms, transit nodes, arc flags, cluster distances, vertex separators, reach, highway hiearchies, etc. Differential heuristics are my favorite for "bang for the buck", as they are fairly low effort (maybe <20 lines of code) for good speedup (3-5X on my game map tests [1]).

There's lots of research papers out there, especially for road maps. I tried keeping track of them all and gave up :-( But you might find these two papers useful:

* https://arxiv.org/pdf/1504.05140.pdf

* https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.p...

[1] https://www.redblobgames.com/pathfinding/heuristics/differen...

amitp··on Google is apparently struggling to contain an ongoing spam attack
I tried googling "What is the fifth book in the wheel of time series" and got

1. Wikipedia - The Fires of Heaven

2. Amazon - The Fires of Heaven (The Wheel of Time, Book 5)

3. a bunch of videos which I skipped over

4. Wheel of Time Wiki - The Fires of Heaven

5. Macmillan Publishers - The Wheel of Time, Books 5-9

6. Goodreads - The Fires of Heaven (The Wheel of Time, #5)

7. Novelnotions - Book Review: The Fires of Heaven (maybe this is spam?)

8. Esquire.com - Wheel of Time Books in Order (not specific to book 5)

9. FictionDb - Wheel of Time Series in Order (not specific to book 5)

10. Barnes And Noble - The Fires of Heaven

I am wondering how different everyone's results must be. [Also, I don't know how to format a list on HN…]

amitp··on "CSS is dramatically more difficult than learning assembly language" [audio]
I'd start with learning the layout model and the selector rules to get the mental model right. A lot of things clicked into place once I had a good mental model.

The main idea for layouts is that the CSS layout properties like width or margin are interpreted based on which layout mode you're in. Some html tags (<span>, <a>, <img>) default to the "inline" mode, where they are put side by side horizontally and wrap to the next line. Some html tags (<p>, <div>, <h1>) default to the "block" mode, where they are put one after the other vertically and "wrapping" doesn't mean anything. There's "inline block" which is inline on the outside but block on the inside. There's also "flex" and "grid" and "table" layouts, and their inline-on-the-outside variants. Each layout mode is useful for different things.

So when I'm frustrated about <span> not honoring width, or margin-auto not working for <img>, it's because the inline layout has word wrap. When there are 2.5 lines of wrapped content, things like width and margin work differently than in block layout mode. Instead of tweaking width/margin, I found it more useful to go back to understanding why it was not doing what I want, and then switch the layout mode to the one that matches my needs. Recommended: https://www.joshwcomeau.com/css/understanding-layout-algorit...

Selector rules are a pattern matching system to assign CSS properties to HTML elements. They also have priorities, so some selectors will have a higher or lower priority than others. These are sometimes useful, sometimes frustrating. I don't have a good reference at the moment, although I see that MDN has a page https://developer.mozilla.org/en-US/docs/Learn/CSS/Building_...

I think of BEM, tailwind, sass, etc. as ways of using CSS once you know what CSS you want, rather than replacing having to know CSS. It's like how React is a way to constructing HTML, but you still have to know what HTML you want to construct. So I wouldn't start with them.

BTW it is a lot of fun to right click on a page, inspect the css, and start tweaking it!

amitp··on Mechanical Watch (2022)
I agree with naet that threejs might be the thing to look at if you want to make 3d animations. My own interactive diagrams are 2d, and I often use svg with reactive data filling in the parameters. [1] I've also tried hand crafting and it's not so bad for pages like this. They're mostly write-once pages, not software that's being maintained for many years. Some of our intuitions are out of whack when they tell us that we need abstractions and frameworks for maintainability.

[1] https://www.redblobgames.com/making-of/circle-drawing/

amitp··on Mechanical Watch (2022)
He's not taking commissions, although maybe he'd make an exception for wikipedia.
amitp··on HN-comments-drawer: one line HN comments integration into sites
I went back and forth but tried it, and looked at the comments I got. I decided I really liked the comments I was getting. Some asked questions. Some offered additional information. Some pointed out mistakes. It's been great!
amitp··on Hexagonal Grids (2013)
Thanks!

For more pages like this, look at https://explorabl.es/ — it's a collection of visual/interactive explanations of various topics

amitp··on Hexagonal Grids (2013)
Also take a look at https://explorabl.es/
amitp··on Hexagonal Grids (2013)
Another one of my favorites has disappeared recently :-(

"the sierpinski triangle page to end most sierpinski triangle pages ™" — but it's still on wayback machine https://web.archive.org/web/20190322201106/https://www.often...

amitp··on Hexagonal Grids (2013)
Spiral and other coordinate systems are on my list of things to add to the page. In addition to the Paul Bourke page, I have these bookmarked:

- https://gamedev.stackexchange.com/questions/71785/converting...

- https://tex.stackexchange.com/questions/275490/is-there-an-e...

- https://github.com/cooscoos/spiral_cube

- https://web.archive.org/web/20160309172431/http://www.pyxisi...

- https://www.sciencedirect.com/science/article/pii/0166218X92...

- https://thoughtstreams.io/jtauber/hex-map-addressing/

- http://tzaphiriron.sidemoon.net/static/hex/hex.html

- https://tilde.zone/@misterdave/109736460410840020

There's so much more to add to the page, and I keep adding over time. Thanks for the link to the hex-spiral crate; I'll add it to my bookmarks.

amitp··on Hexagonal Grids (2013)
I treat it as a "living document" and update it over time, especially to update links. The last few updates:

* 2023-02: used the mouse event techniques I described here: https://news.ycombinator.com/item?id=37703291

* 2023-02: added an interactive calculation of the number of hexagons in a spiral

* 2022-12: rewrote the introductory diagrams after trying out many alternative designs; wrote about it https://simblob.blogspot.com/2022/11/introduction-to-hexagon...

* 2022-10: removed server-side rendering, as it was complicating the build process, and it wasn't a clear win (page loaded slower)

* 2022-07: fixed some embarassing typos in the sample code (ugh)

* 2021-11: updated sample code to be easier to read and not use python-specific constructs; updated naming to be more clear about which code works on cube coordinates vs axial coordinates; filled in missing helper functions that I thought would be obvious but I should've included all along

* 2021-10: unified the hex implementation guide, which used q/r/s coordinate names for cube-hexagon and q/r for axial-hexagon and x/y for cartesian, with the hex theory page, which used x/z/y for cube-hexagons and q/r for axial-hexagons and x/y for cartesian. This was the last major update, as it involved updating all the text, diagrams, and sample code. The unification is something I had been wanting to do for several years but I knew it would take a while and it would also break "backwards compatibility" with everyone who had read the x/z/y version. It was especially tricky because x/z/y not x/y/z corresponded to q/r/s, and that's what led to the embarassing typos in code I had to fix later. And the change in order also changed which direction the rotation algorithm worked.

* 2021-01: updated the size & spacing diagram to visually show the relationships between the different measurements

* 2021-01: changed the hex and axis labels to try to make them correspond because it's a bit confusing; see https://simblob.blogspot.com/2021/01/hex-diagram-labels.html

* 2020-12: added a section about reflections https://www.redblobgames.com/grids/hexagons/#reflection

* 2020-04: improved the labels on the cube/hex diagram to try to improve the correspondence between the diagram and text https://www.redblobgames.com/grids/hexagons/#coordinates-cub...

* 2019-04: rewrote the map storage section because I wasn't at all happy with how it was written before; I wrote up the change https://simblob.blogspot.com/2019/03/improving-hexagon-map-s...

* 2019-02: used IntersectionObserver to delay the diagram rendering until you reach that section of the page; this improves page load times

* 2018-05: added the "doubled" coordinate system. It's a pretty nice system, and I didn't know about it when I first wrote the page. I learned about it from rot.js.

I had lots more changes in 2018. I had just reimplemented the entire page (https://simblob.blogspot.com/2018/04/april-updates-hex-grid-...) and that gave me lots of ideas of things to improve. I first rewrote it without changing the diagrams, but then went back and made lots of diagram and text changes.

amitp··on Hexagonal Grids (2013)
You can briefly see the red blob logo at 7m 37s into the video. :-)
amitp··on Hexagonal Grids (2013)
Tech note (or horror story): the implementation guide's code at the bottom, which is also the code used to implement the diagrams on the the main page, is generated.

I start with hex algorithms written in Haxe. I use Haxe's macro system to turn this into an abstract syntax tree. I then use Haxe's ADT + pattern matching to transform this into a different syntax tree. And then I again use Haxe's ADT + pattern matching to transform this into Python, C++, JavaScript, C#, TypeScript, Lua, Java, and Haxe code. (I also have partial support for Rust and Lisp)

Unlike most "transpilers" I'm trying to generate code that looks reasonably idiomatic for the target language. I transform names and structure (e.g. `hex_add()` for a C global function but `Hex.add()` for a Java class method) and also transform for dynamic types (e.g. Point(x,y) can have numbers in JavaScript but I need a separate Point and FloatPoint for int/float in C++). This means I need to sometimes annotate the original Haxe-syntax code with hints about how it should translate into each language. For example, 1/2 produces a different value in Python (0.5) than in C (0), so I need to add hints to tell the transform code which one I mean.

I also translate the unit tests in this way, and run them as part of the output code.

It's been a fun project but it's grown out of hand. The past week I've been pondering refactoring parts of it.

The reason for all this complexity is that my original goal was to add a language drop-down on the implementation guide page. Then you could read the implementation guide in your choice of language, your choice of grid, your choice of indentation, etc. That was an overly ambitious project :-)

amitp··on Hexagonal Grids (2013)
Thank you!
amitp··on Hexagonal Grids (2013)
Two ways of thinking about pointy vs flat top:

1. Pointy and flat are 60° rotations away from each other. This is what I use for animations. But it's not as useful for the math.

2. Pointy and flat are the same with x/y flipped. This is much more useful for coding.

amitp··on Hexagonal Grids (2013)
Thanks! I celebrate weird hobby web sites. Here are some of my favorites:

* 59828 different definitions of "triangle center" https://faculty.evansville.edu/ck6/encyclopedia/ETC.html

* Amazing reference on bezier curves https://pomax.github.io/bezierinfo/

* Sunbeam radiant toaster http://automaticbeyondbelief.org/

* How to pack geometric shapes inside other shapes https://erich-friedman.github.io/packing/

* Pictures of library cards https://librarycards.tripod.com/id1.html

* All about pc fans https://nick-black.com/dankwiki/index.php?title=PC_Fans

* Cross sections of candy bars https://scandybars.tumblr.com/

* All kinds of info about bicycles https://www.sheldonbrown.com/

* Every type of plastic used by lego https://bricknerd.com/home/every-type-of-plastic-used-by-leg...

* Ian's Shoelace Site https://www.fieggen.com/shoelace/

amitp··on Emacs and shellcheck
Thank you for that package! I was using that at first but then switched to the emacs 29 code.
amitp··on Draggable objects
Cool! I've tried a directive and tried a component (with slots) but I haven't tried a composable, mainly because I wasn't sure how to set up event handlers that way. (I don't have a lot of experience with composables)
amitp··on Draggable objects
One of the map design goals in RotMG was that players could start playing solo on the coasts, and then as they moved up towards the mountains, the area would shrink so they would be more likely to meet each other. However, when we added teleportation the "forcing function" wasn't needed anymore. Players naturally wanted to play with each other. Also, a lot more players were high level so we needed more mountain land and less coastal land. For https://gasgame.net/ we're using a different design, where south is easier and north is harder. Relative to RotMG's map it shrinks the beginner areas and expands the veteran areas.
amitp··on Draggable objects
Context: I had been planning to visit adanto6840 on a road trip planned for March 2020, but then … the pandemic hit and I had to cancel those plans. But one day I will take that road trip :-)
amitp··on Draggable objects
Thanks! One of the big changes when I went from Java applets and Flash applets to HTML5 (around 2011–2012) was that I wasn't limited to only the diagrams being interactive, but I could make the rest of the page interactive too. I can change text and sample code. I can also embed widgets into text and sample code. An example is [1] where you can see the draggable numbers in the text and in the sample code, and those will change the diagram.

[1] https://www.redblobgames.com/articles/probability/damage-rol...

amitp··on Draggable objects
The way this code works, the drag motion updates some state. I can apply constraints when setting the state. Then the state drives the redisplay.

I wanted to separate the constraint system from the event handling system. Libraries like jquery-ui tie them together, so the event handling system has to know all the possible constraints. In jquery-ui, they support bounding box, axis, square grid, snapping to dom elements. But what if I wanted snapping to a hex grid, or a logarithmic scale grid, or a bounding circle? It's not supported.

In the code you'll see "state.pos = …". That's where the state is set. For constraints, I put "pos" behind a setter. Then the setter can apply the constraint, without the drag event handling code having to know what type of constraints are needed.

I should update the page to show some examples of constraints. I completely forgot to mention this aspect of the code recipe. (Thanks!)

I have some older examples of constraints at https://www.redblobgames.com/articles/curved-paths/making-of... and a prevent-collision example at https://redblobgames.github.io/circular-obstacle-pathfinding... . However I haven't tried drag-to-reorder or animated drop targets.

← PreviousPage 2 of 7Next →