[HN Gopher] Draggable objects
___________________________________________________________________
Draggable objects
Author : stefankuehnel
Score : 987 points
Date : 2023-09-29 12:51 UTC (1 days ago)
(HTM) web link (www.redblobgames.com)
(TXT) w3m dump (www.redblobgames.com)
| slowhadoken wrote:
| 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.
| ChadNauseam wrote:
| > I always say his last name like Matthew Patel says his name
| in Scott Pilgrim
|
| One of the seven evil hexes :D
| slowhadoken wrote:
| "PUH-TELL" with the fast Michael Jackson version of the
| Indian head wobble
| djacking wrote:
| [dead]
| PaulDavisThe1st wrote:
| 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/
| wruza wrote:
| What's the rationale here?
| layer8 wrote:
| 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.
| PaulDavisThe1st wrote:
| 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.
| layer8 wrote:
| 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.
| PaulDavisThe1st wrote:
| 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.
| 8n4vidtmkvmk wrote:
| Minimal movement* I allow a few pixels for Shakey slow
| hands.
| hutzlibu wrote:
| 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 ..
| amitp wrote:
| Thank you everyone! What a surprise to be on HN today. Happy to
| answer questions!
| Max_Mustermann wrote:
| Hey Amit! I remember you and your articles fondly from my RotMG
| days.
| dgreensp wrote:
| 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.
| amitp wrote:
| 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.
| tjfjr wrote:
| 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!
| amitp wrote:
| 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/introduct
| ion...
|
| [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...
| gaolei8888 wrote:
| Awesome work! Thanks a lot. It is fun to read these type
| creative articles
| onassar wrote:
| Really gr8.
| birracerveza wrote:
| 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!
| liendolucas wrote:
| 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!
| dang wrote:
| 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?
| amitp wrote:
| 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...
| dang wrote:
| 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.
| sh1mmer wrote:
| 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.
| dang wrote:
| 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&p
| refix=true&que....
|
| But if we're to optimize HN for intellectual curiosity (h
| ttps://hn.algolia.com/?dateRange=all&page=0&prefix=true&s
| or...), 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.
| nayuki wrote:
| 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.
| philipov wrote:
| 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!
| ww520 wrote:
| 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.
| kamikaz1k wrote:
| Unfortunately you can't. That (draggable) API is not designed
| with that use case in mind.
| ww520 wrote:
| You're right. I gave up after getting nowhere. The UX was
| not as nice but it was ok.
| amitp wrote:
| 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.
| ww520 wrote:
| 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.
| collinmanderson wrote:
| 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/API/HTMLElement...
|
| https://developer.mozilla.org/en-US/docs/Web/HTML/Global_att...
| amitp wrote:
| 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.
| penteract wrote:
| 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.
| stefantalpalaru wrote:
| [dead]
| philipov wrote:
| I think I might call RedBlobGames the #1 website on the internet
| for learning game algorithms and data structures. Amit is the
| best!
| nimish wrote:
| Classic website, one of the all-time greats.
| jjkaczor wrote:
| 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/
| amitp wrote:
| Oh wow, FidoNet, that brings back memories. :-) I still miss
| Usenet of old.
| zubairq wrote:
| 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.
| bryceneal wrote:
| 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.
| jart wrote:
| I love this red blob!
| adanto6840 wrote:
| 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! :)
| gowld wrote:
| "If you're in the Silicon Valley area and want to chat in
| person, email me at redblobgames@gmail.com. "
| amitp wrote:
| 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 :-)
| adanto6840 wrote:
| Looking forward to it! :)
| JLangley wrote:
| Love this THANK YOU!
| sarnowski wrote:
| 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.
| marwis wrote:
| 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?
| ly wrote:
| 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
| marwis wrote:
| 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.
| calebm wrote:
| Their hexagon grid page is one of the best hexagon grid resources
| on the web that I've found.
| zem wrote:
| yeah! i clicked through the link and thought "oh, the hex grid
| guy!"
| rgovostes wrote:
| 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.
| amitp wrote:
| 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.
| runarberg wrote:
| 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>`).
| amitp wrote:
| 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)
| runarberg wrote:
| 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).
| ge96 wrote:
| I remember when this was a big deal to me, jQuery days.
| lloydatkinson wrote:
| I've spoke to Amit a lot in the past, very knowledgable!
| dang wrote:
| 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.)
| snapcaster wrote:
| I love Amit! Went through all these articles in college and
| learned so much about programming
| hkxer wrote:
| Drawflow is good
| LorenzoGood wrote:
| I really loved this site when trying to implement A*
| mickeyp wrote:
| 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.
| feoren wrote:
| 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.
| amitp wrote:
| 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/
| drng wrote:
| This almost perfectly describes https://ciechanow.ski/ as well.
| Worth poking through if you haven't seen it before.
| netvarun wrote:
| 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.
| [deleted]
| NeveHanter wrote:
| 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.
| mumintrollet wrote:
| 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 :)
| trees101 wrote:
| I wonder if graph search algorithms such as described on this sit
| e(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?
| trees101 wrote:
| 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.
| VHRanger wrote:
| 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
| trees101 wrote:
| Thank you!!! Comments like this are why I love this site.
| recursivecaveat wrote:
| 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.
| trees101 wrote:
| 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.
| gcr wrote:
| 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.
| g9yuayon wrote:
| 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.
| wildrhythms wrote:
| 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 :)
| [deleted]
| aboodman wrote:
| 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.
| sbayeta wrote:
| Very nice
| tobr wrote:
| > 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.
| Nezteb wrote:
| I was bored so I made a super simple implementation of this:
| https://codepen.io/Nezteb/pen/MWZBapL
| diath wrote:
| That doesn't seem to work in Firefox:
|
| > TypeError: input.getBoundingClientRect is not a function
| Nezteb wrote:
| Womp womp; I'm not sure why. Someday I'll try it out on
| Firefox and maybe fix it.
| orlp wrote:
| Doesn't work with touch.
| Nezteb wrote:
| 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
| ellyagg wrote:
| I thought they meant the object automatically snaps to the
| nearest target in real-time.
| Nezteb wrote:
| 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.
| slowhadoken wrote:
| Same. It's such a simple idea but execution can be brutal. I
| also took drag select for granted for years too.
| pupppet wrote:
| Oof, or drag-to-reorder while supporting nesting.
| alexbock wrote:
| 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.
| 8n4vidtmkvmk wrote:
| Android has the same problem. Sometimes it lets you drop
| inside, sometimes it flies away.
| slivanes wrote:
| 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.
| fingerlocks wrote:
| Just tried this, and you can. But it definitely takes
| more finesse than any other column.
| allenu wrote:
| 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/
| npinsker wrote:
| 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.
| stefan_ wrote:
| 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.
| otikik wrote:
| 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.
| Marazan wrote:
| 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.
| amitp wrote:
| 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/
| gabereiser wrote:
| 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.
| displaynone wrote:
| One thing missing: accessibility. how ought facilitate drag using
| keyboard controls?
| bastawhiz wrote:
| 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.
| nkrisc wrote:
| 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.
| stronglikedan wrote:
| That would be a _moveable_ object, and I reckon it would be
| easy to implement using this as a basis.
| json2d wrote:
| [dead]
| alice-i-cecile wrote:
| These resources are exceptional: I reference the hexagon page
| constantly!
| tsumnia wrote:
| 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
| amitp wrote:
| That's great to hear -- thank you!
| tsumnia wrote:
| 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.
| gowld wrote:
| What's the difference between the approaches?
| tsumnia wrote:
| 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/implement
| ati...
| amitp wrote:
| 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.
| throwaway290 wrote:
| See also slide to unlock game
| (https://news.ycombinator.com/item?id=36138304). I wonder if it
| used lostpointercapture.
| SoKamil wrote:
| 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.
| amitp wrote:
| 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...
| layer8 wrote:
| 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.
| qingcharles wrote:
| Is there a different cancelation key used on other platforms,
| other than ESC that I should handle?
| layer8 wrote:
| 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.
| qingcharles wrote:
| OK cool. Thank you. I'm not a hardcore Mac or Linux GUI
| user so I didn't know if I had missed something :)
| phkahler wrote:
| The page reminded me of Ken Perlins' page:
|
| https://cs.nyu.edu/~perlin/
|
| Yes, the Perlin noise guy among many other things.
| bmitc wrote:
| 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.
| amitp wrote:
| 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.
| evmar wrote:
| 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!
| qiller wrote:
| 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
| michaelwm wrote:
| 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.
| kibwen wrote:
| 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...
| amitp wrote:
| BTW the newer RotMG maps are based on this http://www-cs-
| students.stanford.edu/~amitp/game-programming/...
| amitp wrote:
| 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.
| notsurenymore wrote:
| Doesn't Ark kinda do this, except with elevation, it becomes
| more difficult the more inland you travel.
| Decabytes wrote:
| This is an incredible resource. I will definitely be bookmarking
| this website for the future
| Syzygies wrote:
| 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.
___________________________________________________________________
(page generated 2023-09-30 23:02 UTC)