Draggable objects | Hacker News Reader

Draggable objects

redblobgames.com

1,059 pointsstefankuehnel141 comments

This article is about dragging, and I've run into all of the pitfalls and come to the same solutions that Amit talks about. Excellent article!

One of the hardest things I have needed to code from scratch is drag-to-reorder. It seem so natural from a user perspective, but when you get into inconsistently sized items, having to create placeholders between items, detecting edges, going down rabbitholes of box-fitting algorithms... it's a fun challenge :)

Oof, or drag-to-reorder while supporting nesting.

I've always been surprised that Apple added this functionality to the iOS home screen without having a solution to the reorder vs nesting UI problem. Trying to move an app into a folder often results in the folder deciding to fly out of the way and let the item take its place when you're really trying to drop something on the folder to insert it.

In IOS, I'm pretty sure you cannot add an app that currently sits on the far right of the screen to a folder anywhere beneath it.

Just tried this, and you can. But it definitely takes more finesse than any other column.

Android has the same problem. Sometimes it lets you drop inside, sometimes it flies away.

I have a trick for this that I love that is very general:

1. When a user begins dragging, calculate the layouts for all possible drop targets (or perhaps just those that are currently visible). 2. For each of those layouts record the position the dragged objects ends up in. 3. On each mouse movement, select from those positions the one that's closest to the dragged object's current position 4. Render the selected layout

This ends up feeling really good and works for any kind of complex layout / reflow.

Very nice

I was bored so I made a super simple implementation of this: https://codepen.io/Nezteb/pen/MWZBapL

That doesn't seem to work in Firefox:

> TypeError: input.getBoundingClientRect is not a function

Womp womp; I'm not sure why. Someday I'll try it out on Firefox and maybe fix it.

Doesn't work with touch.

I'm not surprsied. I suck at CSS and just wanted a basic/brittle example that worked in Chrome. Anyone is free to fork my CodePen and make it better though. :D

I thought they meant the object automatically snaps to the nearest target in real-time.

The person who described the algorithm made it that way, but I added a `const closeEnoughToSnapDistance = 200` to make it more like Trello; once you get close enough, it will snap.

> record the position the dragged objects ends up in

Can you explain this in more detail? Don’t you need to actually change the layout to figure this out correctly? Or are you approximating it with the top/left corner of the current element in the same place or something?

EDIT: I read to fast, for some reason I understood step 1 as figuring out the location/bounding box of each drop target, but I think you mean to actually put the dragged object there and let the browser compute the layout.

Yes, that's what I mean.

I had to tackle this problem for my index card app, Card Buddy. [1] It was definitely a fun challenge and I still found a better way to do it later.

What I ended up doing is when you pick up a card, I compute the layout as if the card was deleted from the board, and then it becomes easy. Wherever you hover the mouse, I just displace whatever is there.

There were still tons of edge cases I had to work out, though, especially when you start editing a new card that hasn’t been “committed” to the data model yet. I had to add the option to shift existing cards out of the way to make room for a phantom card.

It helps to recognize that there are just lots of edge cases you have to manually handle. If you try to tackle it as though there’s a more generic/homogeneous solution, you end up going around in circles a bit with the design. I should probably create a blog post on all the different edge cases.

As I said, though, I found an even better way to do my layout, which saves on unnecessary computations and makes the layout engine more flexible and user-friendly. (It’s amazing what a difference your choice of data model representation makes on your solution.) It’s been a fun puzzle to solve!

[1] https://www.ussherpress.com/cardbuddy/

Same. It’s such a simple idea but execution can be brutal. I also took drag select for granted for years too.

The article doesn’t seem to discuss cancellation. For example, there is the convention (at least on Windows) that pressing Escape cancels the dragging. Sometimes you also want to cancel the dragging when the mouse-up happens outside of some defined area. Cancellation serves as a quicker Undo (or an “oh, I actuality didn’t mean to drag”) for the user. In any case, this means that you have to save the original state at the start of the dragging, so that it can be restored if the dragging is cancelled, even if you otherwise provide no Undo functionality.

In the case of cancellation-when-dragging-outside-an-area, there’s also un-cancellation, meaning you resume the dragging when the pointer returns to the area, after the state visually reverted to the original one while outside the area (to indicate to the user that a cancellation would happen if the mouse button is released at that point). Or put differently, the real cancellation only happens upon mouse-up, but is already visually indicated while dragging.

Is there a different cancelation key used on other platforms, other than ESC that I should handle?

I’m not aware of any. What I meant to say is that I don’t known if that convention of cancelling drag&drop with Escape is as established on Mac and Linux as it is on Windows. But using the Escape key to indicate cancelling (e.g. a dialog) is pretty universal in GUIs, I would say.

OK cool. Thank you. I'm not a hardcore Mac or Linux GUI user so I didn't know if I had missed something :)

>Sometimes you also want to cancel the dragging … outside of some defined area.

But that Windows <<SNAP>> when you drag something too far so the dragged object and the pointer just suddenly disappears, and snaps back to the original position without warning!

Can’t believe Microsoft still believes that is smart UI design. It utterly confuses users. You may even see them caught in a yo-yo situation or just scared to release the left mouse button while they don’t know what’s happening

Cancellation is a huge often overlooked issue - I agree with you and it’s not a simple issue. Common users don’t know that ESC can help.

One extra detail, something I've learned from 20 years of working on dragging all kinds of objects around the GUI of Ardour [0]: handle ALL button press and release events as drag events where there is no movement. That is: press ALWAYS starts a drag that is finished by the release, and the code that handles release "special cases" the no-movement condition.

[0] https://ardour.org/

What’s the rationale here?

Having separate code paths for "it's a press", "it's a release", "it's a drag" just turns into a nightmare when you actually use all 3 input events extensively. Remember that while the motion events of the drag might be the visually interesting part, for the most part the interesting stuff happens at the beginning and end of them - i.e. the press and release.

It becomes massively simpler conceptually (and even in the code) to treat any button press as a potential drag, and a simple click becomes just a drag-with-no-movement.

Minimal movement* I allow a few pixels for Shakey slow hands.

This reminds me a bit of how double-click works, or originally worked: A single (first) click selects the element, and if there’s a second click within a short timeout period on the selected element, it invokes a default action on that element. Meaning, the double click is not a separate type of operation, it’s a continuation of what happens on a single click. You don’t wait after a single click to see if it becomes a double click; instead you always perform the single-click operation (selecting the element), and a second click that makes it a double click may or may not follow, and if it follows is compatible with the single-click action.

Historically, it differed on different windowing systems. The two versions featured the following event sequences:

A: button press, button release, button press, button release

B: button press, button press, button release

This subtle difference leads to a world of difference in mid-level code.

Yes. However, if you select on the first button press (which I think is the usual behavior?), then it shouldn’t matter if you get a corresponding button release or not.

Option B allows to implement an “incompatible” single-click action, with the trade-off that it must be bound to the button release, not the (first) button press.

That should also work, but I did not do it this way and had no problems after I got the basics right. I have general mousedown and mouseup handlers and use a timeout(~150 ms, but configurable), to determine if we deal with a click, or start dragging (or other things). And on mouseup (or if the mouse leaves the screen) and there is dragging in progress -> stopdrag. So dragging for me ist just one of different special cases ..

In the distant past, there was this NSF-funded geometry center in Minneapolis. There was a computational group theory conference (these guys are over the top) and they invited a few mascots from neighboring fields. I had written a system for algebraic geometry, and got an invite. I'd get up really early in the -20F cold to insure a Silicon Graphics workstation for the day, and set about coding a game to better understand group generators and relations.

It involved dragging.

I loved the 2am conversations that resulted. My idea was that dragging need not respect real-world physics. Dragging should feel like a great tab of acid. And everyone was into this, everyone had ideas.

The article implements relatively basic dragging (notwithstanding the several edge cases that arise with web browsers). Are there resources on dragging with constraints such as snapping to guidelines, preventing collisions with boundaries or other objects, or animated drop targets that resize or move in response to the drag operation?

I once wanted to make a customizable Pomodoro timer UI based on subdividing a circular clock into wedges of different durations to define your focus/break intervals. I didn't get very far trying to implement drag-to-reorder of the wedges.

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.

I owe my thanks to this site too. When my team was designing our hexagonal system for geographical analysis back in Uber, I referred to https://www.redblobgames.com/grids/hexagons/ a lot.

Great write up for all the pitfalls and gotchas that come up when dealing with proper interactions

For something more "out of the box", I've been using interactjs for quite a while for a variety of my projects

Thank you everyone! What a surprise to be on HN today. Happy to answer questions!

No, thank YOU. This is an awesome resource for learning game algorithms, and it's a lot of fun to just play around with the interactive explanations.

Definitely one of the best websites I know. Cheers!

Can you please nominate a specific URL on your site that we can change the top link to? (see https://news.ycombinator.com/item?id=37707904 for why)

What's your most interesting piece that hasn't gotten sufficient attention yet? I believe HN has had many great threads about the A* and hexagonal grid articles over the years. Is there a comparable one that's been overlooked so far?

This year I've mostly been updating existing pages in small ways (examples: [1] [2]). This week I've been fixing broken links, which isn't a good HN submission.

I think the best candidate is https://www.redblobgames.com/making-of/draggable/ . It's from earlier this year and hasn't been posted to HN yet (I think).

[1] https://simblob.blogspot.com/2023/04/explaining-hexagon-layo...

[2] https://simblob.blogspot.com/2023/04/improving-mapgen4s-boun...

I've changed to that page from https://www.redblobgames.com/. Thanks!

Obviously, many comments on the thread predate this change, but there's enough context here for readers to figure that out, and hopefully we can get a more specific discussion going.

FWIW, dang, while I know guidelines are to post specific things for me personally “check out this collection of interactive tutorials” is actually a lot more interesting/helpful than linking to a single tutorial, especially when it’s not clear from that tutorial it’s part of a collection larger collection.

Generally I feel like links to collections of stuff do well when they are interesting and don’t when they aren’t and that you modding to a specific example isn’t actually improving quality.

I hear you and am certainly not denying the usefulness of the site! it's fabulous and has been fabulous for many years. It has also made many great appearances on HN over the years: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que....

But if we're to optimize HN for intellectual curiosity (https://hn.algolia.com/?dateRange=all&page=0&prefix=true&sor...), we have to consider thread quality, and there's no doubt that submissions like this generally lead to generic, and therefore shallow, discussion in the way that I described upthread.

Overall I think the best way for HN readers to discover a site like this is bottom-up: to run across an example of a great article and a great thread about it, and then click around to discover what else is there. This is more in the intended spirit of HN.

Edit: it's a little unorthodox for us to change the URL in midstream after a submission has this many upvotes and pre-existing comments, but I hope everyone understands that I did so to give the site more exposure and appreciation, not less. The alternative would have been to downweight the post as a "list submission" (https://news.ycombinator.com/item?id=37707904), and I didn't want to do that.

I appreciate your work and all, but this URL change disoriented me. I upvoted the submission when it was pointing to the root page of the website.

Coming back to the thread half a day later now, I suddenly found that I upvoted the page "Draggable objects" despite never having previously visited or hearing of the page.

I read the new page anyway and liked it. But it contradicts the original my intent of the upvote and essentially gaslights me into a fictitious past.

I'm building out menu systems and information panes for a hobby game right now, and was just starting to wonder about how to make them draggable, so this is exactly the topic I needed. Thank you!

Hey Amit! I remember you and your articles fondly from my RotMG days.

Awesome work! Thanks a lot. It is fun to read these type creative articles

Very neat! The way that you precisely get to the point and then snippets are presented and discussed is fantastic. I wish to see more of these kind of detailed explanations everywhere. Code is read and understood effortlessly!

That is a fantastic discussion on dragging with Javascript. Really appreciate the information.

I've a quick question. How do you restrict the dragging movement to an axis using the built-in DOM events like dragstart/etc. I had a drag & drop feature implemented using the dragstart/dragenter/dragover/drop/etc events. I couldn't find a quick way to restrict the dragging movement to the x-axis. JQuery's drag and drop API used to support it. I'm trying to use the native DOM events/api only. Any information or pointers are greatly appreciated.

Unfortunately you can’t. That (draggable) API is not designed with that use case in mind.

You’re right. I gave up after getting nowhere. The UX was not as nice but it was ok.

I don't know how to do that with the built-in drag-and-drop API. With mouse or pointer events:

1. When I get the event, I update the underlying state, but leave the DOM element alone.

2. I can apply constraints to that state. To restrict dragging to the x-axis, I would never change y.

3. I use the state to drive the redisplay of the DOM element.

Some examples of constraints I want: https://www.redblobgames.com/articles/curved-paths/making-of...

I think jQuery's drag and drop API is using the mouse events directly and not using the built-in dragstart/etc., and that's why they can apply constraints.

I see. Thanks for the info. It seems the problem is that the item being dragged is a temporary image copy of the source element, not the source element itself. That makes controlling the position of the source element irrelevant. Needs to somehow control the position of the temporary image copy to make it work. But anyway it’s a good learning exercise. Thanks for the discussion.

Really gr8.

Have you looked at html's built-in draggable="true" attribute and drag events?

Are there shortcomings with the built-in feature compared to your code?

https://developer.mozilla.org/en-US/docs/Web/API/HTMLElement...

https://developer.mozilla.org/en-US/docs/Web/HTML/Global_att...

I'm not Amit, but from the article:

> Note that this is not the HTML Drag and Drop API, which involves dragging an element onto another element. For my diagrams, I’m dragging but not dropping, and the scrubbable number example shows how I’m not necessarily even moving something around. So I need to read the mouse/touch events directly.

The drag and drop API is doing a different thing that isn't always appropriate - you can get it to do roughly what this article is talking about by making the thing being dragged invisible just after the dragging starts, but it can shrink things and doesn't let you edit them as DOM nodes after the dragging has started. It also lets you drag something out of the browser window and try to put it into a completely different window.

Many of the interactions I'm working on aren't about dragging elements, but instead using the drag motion to do some action. I also had trouble getting the drag-and-drop API to work inside SVG elements. I think it's solving a different problem than what I'm trying to use it for.

Does redblobgames.com have its own RSS/Atom feed? In its footer there is a link to the feed for your other blog, simblob.blogspot.com. I'd love to keep tabs on both of these blogs in my feed reader.

Big fan of your writing, btw!

Thanks! The short answer is: no.

The longer answer is: I'm not actually sure how to solve this problem. The second site, simblob.blogspot.com, is an actual blog. It's time ordered. It has posts. But the main site, redblobgames.com, is structured as a "living document" site, not as a blog. Things are not posted in order.

I could try an automated feed that looks for any changes on pages. But I make small changes all the time. For example on [1] I changed "So far we’ve made step have the same" to "So far we’ve made steps have the same". I've been fixing a lot of broken links and typos this week, so there are lots of pages that have changed, but not in meaningful ways. I don't want those showing up on the RSS feed.

The second problem with an automated feed is that I have pages that aren't meant for publication. I collect notes for myself before I write an article, sometimes for years. For example [2] is something I may never get around to publishing. I don't want new pages to show up on the RSS feed, because most of them aren't ready yet, and some may never be.

So an alternative is for me to manually add entries to an RSS feed when they're "meaningful". I'm trying to do this by posting to the simblob.blogspot.com blog. An example is [3] where I describe the changes I'm making to the mapgen4 page. These wouldn't have been picked up by an automated feed because the HTML didn't change, but the interactive part did, so I wrote about it. Another example is [4] which is about changes to the hexagon page. I'll also go into a lot more details about why I made those changes [5].

But manually writing blog posts means there will be changes that won't show up in the RSS. Ideally I'd have some kind of automated way to flag meaningful changes to the site, but until then I am trying to write meaningful changes on the blog.

[1] https://www.redblobgames.com/pathfinding/a-star/introduction...

[2] https://www.redblobgames.com/articles/probability/loot-drops...

[3] https://simblob.blogspot.com/2023/04/improving-mapgen4s-boun...

[4] https://simblob.blogspot.com/2023/04/explaining-hexagon-layo...

[5] https://simblob.blogspot.com/2022/11/introduction-to-hexagon...

I used to write browser UI code all the time, but it’s been a few years. This is the first I’ve heard of someone using pointer events.

Do you worry at all about someone’s browser not supporting them, given that Safari added support in 2020? I guess Safari 12 is hopefully no longer used in practice, with macOS Mojave users hopefully running Safari 13 or 14? It would be pretty bad if something as simple as dragging didn’t work in a production app designed for the market of web users at large.

Adding event handlers to the document during a drag is a time-honored practice, and browsers add brand-new features all the time that are intended to simplify some use case or other but have their own edge cases and gotchas, which the article says are not fully addressed. And there’s still a combination of pointer and touch events in the end result. I wonder if the “simplicity” in the sense of less code is worth the additional edge cases, less browser support, and the developer needing to understand the ins and outs and browser differences of pointer events, which are presumably less understood and documented than mouse events.

I don't worry about it. I usually wait a few years before using some browser feature. I'm not writing a production app and I have no customers. If I had customers, then I'd be looking at what browsers they use and making a decision based on that.

This page is not prescriptive: I'm not trying to tell everyone else what to do. This page is descriptive: I'm trying to document what works for me. For the use cases I need on my pages, pointer events cleared up a lot of glitches and edge cases I previously had with mouse+touch events. There are some that remain. I'm happy with the switch. This isn't a luxury everyone has. Not all use cases are as well supported as the things I want to do.

Thanks!

One thing missing: accessibility. how ought facilitate drag using keyboard controls?

That would be a moveable object, and I reckon it would be easy to implement using this as a basis.

Overwhelmingly, the answer is "you don't." Your UI should provide alternatives to dragging that allow folks who can't use a point/touch devices to interact with your page. Which is to say, don't shoehorn keyboard support into your drag implementation, add separate keyboard functionality that makes sense in addition to drag functionality.

I think that's a bit off base here. It's like asking how does a keyboard user facilitate click-and-hold to pan the canvas in a drawing program? They don't. Panning with the mouse (or dragging objects) is one interface. The task is panning the canvas, the means to achieve that are varied.

In my example, the answer to the question about accessibility is to additionally provide keyboard controls to complete the task (preferably ones that don't - or optionally don't - require holding a key). For example perhaps a key shortcut to enter a pan mode, in which the arrow keys move the viewport around the canvas. Problem solved.

As for draggable objects, the task is re-ordering. How do you make that accessible? Provide an alternative means to re-order objects, perhaps using TAB to cycle focus through the objects, then a key to select the focused one, and use the arrow keys to move the drag preview to the nearest valid position in that direction.

tab / space / enter to select an item, crtl + arrow keys to move the "dragged" element. Obviously, it can only move one block per keystroke.

Love this.

I was just implementing dragging an SVG element in a Vue app earlier this week, and had to discover pretty much everything the author describes in the article, even in the same order the author describes them, and ended up with pretty much an identical component to do so (except I wrote a composable utility `useDragging` instead of a functional component `<Draggable>`).

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)

I think a directive is actually a better idea. With a composable I basically just accept a ref of the target element and set up the event handlers directly on it (with useEventListener composables).

The page reminded me of Ken Perlins' page:

https://cs.nyu.edu/~perlin/

Yes, the Perlin noise guy among many other things.

I always wish there was more specification surrounding his Perlin noise algorithm he has on his website. For example, asking what the range of output values is does not have an easy answer.

I agree, more should be written about Perlin Noise range. You might find this useful: https://digitalfreepen.com/2017/06/20/range-perlin-noise.htm...

In addition to range I'd like to see the distribution, especially with multiple octaves of noises added together. I haven't found a good page about that.

Off-topic a bit, but I've been curious about a 2D pathfinding problem for a while that this site doesn't seem to tackle despite having lots of articles on the subject. Is there an algorithm out there for finding "enclaves" (i.e. places where you might want to place rewards, spawn the player) within a large 2D terrain grid?

Not super precise, but given a 2D boolean array of pathable/unpathable cells, say generated by Perlin noise, find locations that are only accessible via a relatively narrow "choke point". Example: https://imgur.com/a/jFPXlS5

Standard pathfinding algorithms don't provide enough information to do this, but maybe there's some kind of heuristic approach that could work well.

Lots of pathfinding solutions prefer to work with connected convex polygons (since inside the polygon, you can always go straight to every other point inside). You could merge your cells into these polygons and then filter for small ones by area, I guess.

Brute force and ignorance approach:

Choose random starting point and compute distance to all other points on the map. Repeat for multiple random starting points.

Average the distance.

Points with high average distance are difficult to reach.

You are not trying to find a "path" since you don't have a starting point - you only have end points. Your enclaves are more defined by the shape of the walls (roughly x cells in radius) than with the fact that you reach them through chokepoints. After all, a chokepoint can be just a small door in an otherwise big corridor, separating two big areas. And by concentrating on chokepoints you will lose all the "isolated islands".

You might be luckier treating this as a "map treatment" problem. An algorithm that does things to the whole map, and then reads the result.

For example:

  1. Start assigning a score of 0 to all map cells.
  2. For every cell in the map, set to 1 if it's in contact with any walls
  3. Then add 1 to every cell of the map if it contacts a cell with a non-zero value
  4. Repeat the above step n times, where n is the average "radius" of you enclave rooms.
  5. Every cell with a score of n or higher is a "candidate". For every candidate:
    5.a Check that none of the cells around have a bigger score. If so, move on to the next candidate
    5.b Check that there's no "treasure" around it in a circle of radius n
    5.c You have found the center of an enclave. Mark it with "treasure" and move on to the next cell.

Find starting point in dungeon. A* to every room. Rooms with a large distance (iter count) and with only one or two paths out (choke points, use graph to see edges) become potentials, every potential that is _far & narrow_ is flagged “enclave” with rewards increasing by distance to start.

This is one way to approach the problem. The other way is to do prefab rooms and when generating your dungeons, randomly select one or two prefab enclave rooms to throw into the shuffle. Shuffle the rooms and spread them out then connect hallways and such. This is the approach that Enter the Gungeon took.

Another approach is what @otikik describes. Tracing the walls buy assigning a value to the cells that can then be scored. Minesweeper style.

Tarjan's Algorithm can be used to find choke points, although I haven't tried it myself [1]. I think what I would try is Breadth First Search with multiple start points to calculate various metrics for the map [2] and maybe All-Pairs if you need more [3]. For example, you might use Tarjan's or All-Pairs to find the most commonly used corridors, and then use Breadth First Search from those "central" points to find the "farthest from central corridor" points.

[1] https://old.reddit.com/r/roguelikedev/comments/dc4orn/identi...

[2] https://www.redblobgames.com/pathfinding/distance-to-any/

[3] https://www.redblobgames.com/pathfinding/all-pairs/

Apart from the excellent subject matter, I often pull up this site during UI/UX discussions. Amit clearly has the ability to do really advanced JavaScript visualizations, but he only uses it exactly when necessary. Most of it is a plain document like you might write in Markdown, but when he uses JavaScript, it's illuminating, connected to all the other examples, and clean. Any animation he uses is clearly initiated by the user, and is there not because it looks cool, but because the intermediate frames help the user understand what's happening. It also never moves the rest of the layout around. I go back to this site any time I'm pondering how to do good online documentation, interactive help, tutorials, or even text-heavy presentation of results.

This almost perfectly describes https://ciechanow.ski/ as well. Worth poking through if you haven't seen it before.

100% agree! Bartosz Ciechanowski along with Amit Patel are national treasures. Their expository writing coupled with ChatGPT do dig into some of the more salient points has been a complete game charger for my self learning.

Thank you! I treat them as documents, with some interactive elements. I tend to avoid traditional animations because they're outside the reader's control. I want the reader to be able to pause, slow down, speed up, rewind, etc. One thing I'm going for but haven't completely achieved is that I want the diagrams to be useful even before the interaction.

I am collecting some of the design elements here: https://www.redblobgames.com/making-of/little-things/

I remember when I got back into programming, this site was one of the things that really made me excited to code + develop a deeper understanding of algorithms :)

Amit Patel is the man. I always say his last name like Matthew Patel says his name in Scott Pilgrim. Side note: Sebastian Lague is great too.

> I always say his last name like Matthew Patel says his name in Scott Pilgrim

One of the seven evil hexes :D

"PUH-TELL" with the fast Michael Jackson version of the Indian head wobble

I think I might call RedBlobGames the #1 website on the internet for learning game algorithms and data structures. Amit is the best!

Am going to chime in as well - Amit is amazing and has been providing his knowledge and experience since the early 90's, when I first encountered him on FidoNet over BBS, then next on Usenet.

Regular tech blog: https://amitp.blogspot.com/ Game Dev blog: https://simblob.blogspot.com/

Oh wow, FidoNet, that brings back memories. :-) I still miss Usenet of old.

Agree - I was active enough on Usenet that at one point a book publisher sent me a box of books because apparently I had helped out one of their authors, and he asked them to do so. (Wiley FTW)

A fantastic site. When I originally took over teaching Intro to AI, I initially relied on the A* search closed/open set pseudocode explanation[1]. However, when it would come time to ask students to implement it, I was constantly finding students absolutely confused by the approach. Once I swapped over to Amit's A* explanation, the number of confused students dropped significantly. Forever thankful for their walkthrough.

[1] https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode

What's the difference between the approaches?

Amit describes the differences here [2], but briefly:

- The Wiki pseduocode uses Set data structures for everything. While these are covered in classes, the up-tree concept isn't as heavily described as other trees

- Looking at it now, it looks like the pseudocode is a little more beginner friendly, but "back in mah day" it was not

- Although, RedBlob's pseudocode for obtaining neighboring nodes is clearer than "for each neighbor of current" (Wikipedia pseudocode)

- RedBlob uses Priority Queues and Maps instead of Sets, which connect better to other AI searches / recommendation algorithms. Higher 'priority' recommendations move to root in PQs while nodes in Sets... don't... they just sort of 'exist'

- The Maps make looking up node costs more intuitive than lists (aka "current := the node in openSet having the lowest fScore[] value")

[2] https://www.redblobgames.com/pathfinding/a-star/implementati...

1. I use words for variable names instead of single letters like the textbooks do. I use "priority" instead of "F", "cost_so_far" instead of "G", "heuristic" instead of "H", "cost" instead of "w", "frontier" instead of "OPEN" or "O", "visited" instead of "CLOSED" or "C", "current" instead of "u", "next" or "neighbor" instead of "v".

2. The textbooks use an "open" and "closed" set. But in code, these aren't explicitly stored in set data structures. Instead, they're implicit. The cost_so_far dict(map) contains as keys both the open and closed sets, and the frontier (priority queue) contains the open set. So in my explanation of A* I focus on these data structures (priority queue and dict) instead of the open/closed sets. And when I do talk about the sets, I talk about the combined open and closed sets, calling it "visited" or "reached", because it's the combined set that is actually in the data structures.

3. The textbooks use a priority queue with reprioritization. When you visit a node that has a lower cost than the previously found cost, you go into the priority queue and adjust the cost. In my presentation I don't use reprioritization. Instead, I insert another entry into the priority queue with the lower cost. This makes the priority queue simpler (reprioritization is complicated). And in practice, I think it's faster too.

That's great to hear — thank you!

No thank you! If you're ever near the NC side of the US let me know, I'll gladly buy you lunch for all the help you've given me.

I remember when this was a big deal to me, jQuery days.

Amit was an instrumental part in the development of one of my favorite video games, Realm of the Mad God. It was a masterpiece of the Flash game genre, and its guild feature introduced me to many lifelong friends.

RotMG has a great idea that I wish more games would copy: difficulty scales with elevation. If you want to take it easy, stick to the coasts. If you want a challenge, strike inland towards the mountains (or follow a river upstream). It's a great way of intuitively expressing difficulty ranges across a sprawling world map, and I remember being disappointed the first time that I played Skyrim that it didn't seem to do the same.

For posterity, here's Amit on map generation: https://simblob.blogspot.com/2010/01/simple-map-generation.h...

Doesn’t Ark kinda do this, except with elevation, it becomes more difficult the more inland you travel.

BTW the newer RotMG maps are based on this http://www-cs-students.stanford.edu/~amitp/game-programming/...

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.

Likewise, Amit is phenomenal and the content (and especially its presentation) is really second to none. The value he places on ensuring links stay working, and that content is accurate and updated — is truly phenomenal and almost inconceivable these days.

I’ve also always enjoyed every (virtual) interaction I’ve had with him, however brief — and appreciate that he remembers me and the problems/challenges we faced in my games.

SimAirport and SimCasino very likely wouldn’t be the same (or would have taken much longer to achieve, at best) without his content.

Just a class act; one of these days I’d love to buy Amit a beer or a coffee. My invite doesn’t expire, perhaps next time you’re in the area! :)

"If you’re in the Silicon Valley area and want to chat in person, email me at redblobgames@gmail.com. "

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 :-)

Looking forward to it! :)

This is a great resource and a perfect example of what clear explanations, code and visual aids can do to help you learn a wide range of algorithms.

Great article! Yeah, I can remember going through a hugely painful time trying to get drag and drop working between the web version of an app on PC, tablets, and phone. I think I dropped the phone support in the end though due to the fact that dragging and dropping just didn't feel right on the phone, tapping felt more natural.

A bit off topic, but this site looks great! I see it has many great articles about algorithms with interactive visualizations. Why I didn't know this site before?!

Anyone has some more recommendations of sites with similar content (easily explained algorithms with great interactive visualizations? )

Do graph search algorithms have applications for strategy? https://www.redblobgames.com/pathfinding/a-star/introduction... Consider a game like age of empires. The cost of attacking a village goes up when a wall is built around it. But when canon are invented, the cost goes down. Can we model each map (before and after invention of canon) and use it to plan a strategy? Same for building a port , portal or airport.

That's effectively search on the decision tree. There's a lot of research on this!

Look into Montecarlo tree search, CFRM, AB pruning, and also more recent deep learning methods.

It's a very exciting area of research

Thank you!!! Comments like this are why I love this site.

I would guess it's probably not worth it because "how much do cannons improve my overall position" is a tricky question, and making a really intelligent and sophisticated answer is not really visibly distinct to players from a stupid heuristic like a sigmoid function of how many walls the player has built. It's an amusing curiosity that you can build stupid walls and trick the AI into researching the tech, but it's better to make those walls you're paying for useful, so you can rely on that being generally true.

I think a lot about some advice I heard from the creator of Brogue. Essentially players have a tough time figuring out how AIs make their decisions and often assign complex motives to them when they don't exist. His example was he coded archers to try to maintain a position in some range band from the player as their primary motivation in a vacuum. The community would assign all sorts of supposed logic to archer behavior because in real-world environments with extra geometry or extra situational AI routines they couldn't see behind the curtain. Additionally, that most game AI exists to create a fun experience for the player, we only make it try to play well in service of that goal.

I agree, it seems tricky to actually quantify. The hard part is to create the graph in the first place, before you start the graph search. There must be methods for creating simplified approximations.

speak of the devil! i've been putting together a little board game in Godot in my free time, and just finished devouring all of the hexagon content this week.

Amit's work is awesome! Right up there with Inigo Quillez's site on graphics in terms of informativeness and fascination in his own domain.

Playing around with a hex based game myself, the bookmark to the Hexagonal Grid is a constant companion over the years. It was updated slightly over the years with some visual cues. Amazing presentation, and so great to learn.

I love this website! It was the place I've understood how A* is working in early 2010s when I started getting into more advanced "standalone" (w/o GameMaker/TGF) gamedev.

These resources are exceptional: I reference the hexagon page constantly!

Amit is a treasure. I referenced his articles many times when making my own games. We could really use more thoughtful and friendly visual learning resources like this for other subject matter.

Is there any way to reduce lag between pointer and draggable?

I once tried throttling updates via requestAnimationFrame but it didn't help much. Perhaps movement prediction?

The cursor is often rendered with special GPU acceleration like when using Hardware Cursor, making it as responsive as possible, but that does mean there’s always going to be a slight delay for the draggable object

But this doesn't happen in native UIs. I think this is because JS event handlers are asynchronous and not running within native event loop.

The way Windows handles it seems to be that hardware rendering of the pointer is turned off when you drag around windows. It was very obvious when I was using f.lux, the bright white pointer would turn yellow like the rest of the screen when dragging.

Maybe you could try turning the actual cursor invisible when dragging and instead render a custom drag cursor parented to the object being dragged.

This idea in which you select a checkbox to highlight specific parts in code is actually a pretty good UX which I have never seen before.

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...

I love how half the comments on here are about what a nice person the author of the site is. I, too, have had only positive interactions with Amit!

Their hexagon grid page is one of the best hexagon grid resources on the web that I've found.

yeah! i clicked through the link and thought "oh, the hex grid guy!"

I wonder if graph search algorithms such as described on this site(https://www.redblobgames.com/pathfinding/a-star/introduction...) have applications in other strategies.

Consider a game like Age of Empires. In the beginning you might be able to defend your village by building walls around it. For an attacker, there is a high cost to go through the wall. But when cannons are invented, suddenly the cost of going through the wall drops.

Is there a way to model this? Can you draw a graph of the terrain that looks different before and after the invention of cannon?

Classic website, one of the all-time greats.

I love Amit! Went through all these articles in college and learned so much about programming

This is an incredible resource. I will definitely be bookmarking this website for the future

I've spoke to Amit a lot in the past, very knowledgable!

See also slide to unlock game (https://news.ycombinator.com/item?id=36138304). I wonder if it used lostpointercapture.

I really loved this site when trying to implement A*

I love this red blob!

Love this THANK YOU!

Drawflow is good

It's a great site, but the home page of such a site doesn't make for a great HN submission because it falls in the category of "list": https://hn.algolia.com/?dateRange=all&page=0&prefix=true&sor....

Lists don't make great HN submissions because they don't point to anything specific enough. The resulting discussion tends to be generic and shallow, because the only material to discuss is the lowest-common-denominator, i.e. whatever the items on the list have in common.

This thread is a nice example because the comments are only about the site in general—mostly how good it is—which of course is true, but not 'interesting' (in HN's sense of the word) enough to devote a frontpage slot to (https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...).

The solution is to pick the most interesting element from the list and submit that instead. Maybe we should ask amitp to nominate one :)

Edit: I did that and have changed the URL now. See https://news.ycombinator.com/item?id=37708834. (I will also mark the current comment off topic so it goes to the bottom of the page.)

Reply on news.ycombinator.com