Checking for mouse over irregular shapes

General discussion about LÖVE, Lua, game development, puns, and unicorns.
User avatar
bartbes
Sex machine
Posts: 4946
Joined: Fri Aug 29, 2008 10:35 am
Location: The Netherlands
Contact:

Re: Checking for mouse over irregular shapes

Post by bartbes » Sun Apr 11, 2010 9:54 pm

Wow, that was some explanation!

User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: Checking for mouse over irregular shapes

Post by kikito » Sun Apr 11, 2010 10:01 pm

I'm also impressed.
When I write def I mean function.

User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Checking for mouse over irregular shapes

Post by vrld » Sun Apr 11, 2010 10:54 pm

3.5th solution:
Create the grid, but postprocess it using a Quadtree:
Start with the whole area as the root node of the tree.
Create the nodes recursively:
[*] If the depth of recursion is > N (say 6, experiment on that), stop
[*] If the node covers only one shapre, stop
[*] if the node covers more than one shape, divide into four equally sized rectangles an recurse

This will reduce the amount of required memory to store the pixel->shape association and will still be fast.
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine

User avatar
nevon
Commander of the Circuloids
Posts: 938
Joined: Thu Feb 14, 2008 8:25 pm
Location: Stockholm, Sweden
Contact:

Re: Checking for mouse over irregular shapes

Post by nevon » Mon Apr 12, 2010 7:26 am

vrld wrote:I think Shape:testPoint will do exactly the same: Test if the point is right of every edge in the polygon.

Anyway, for understanding the right-of-test: [...]
Whoa! Thanks for that explanation. I'm going to have to process this for some time before I can even begin to understand it.

Anyway, I went with the Shape:testPoint solution, and it's working great! Thanks for all the help, everyone!

pekka
Party member
Posts: 206
Joined: Thu Jan 07, 2010 6:48 am
Location: Oulu, Finland
Contact:

Re: Checking for mouse over irregular shapes

Post by pekka » Mon Apr 12, 2010 9:49 am

pekka wrote: First of all, making a grid that divides the space is actually a good solution. But you need to have some fancier logic to get the hit testing be pixel perfect inside the grid sections, or at leat reasonably close to pixel perfect anyway. I'll describe that a bit.
vrld wrote: The search [in trapezoidal maps] is performed in O(logn) time, which for a large number of edges will be considerably faster than pekka's solution.

The grid approach is way easier to implement and will even be faster than trapezoidal maps, but it will also require a lot more memory.
I would just like to point out that "my solution" did in fact include the possibility of using a grid, as it says right on the top of my message. I would also appreciate it if you differentiated between the terms asymptotically faster and measurably faster in your future messages. (The latter term can be used after you have taken measurements of how actual working code performs.)

You see, my religion forbids me from believing in other forms of faster. :) :)

User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Checking for mouse over irregular shapes

Post by vrld » Mon Apr 12, 2010 10:42 am

I did not want to step on your toe, but as my religion forbids to think there is a great difference in the two types of fast (I do not believe in cache effects and other such blasphemous notions of actual physical machines):
A O(logn) solution is measurably faster than a O(n) solution. Additionally, computing intersections between line segments would be slower than walking down a tree, or am I missing something?

Anyway, a fourth (kind of hackish) take on the problem:
As you already have to have your map in memory, you can use it to determine the clicked shape.
Color each shape different. The difference can be very slight, say from #fea104 to #fea103, as the eye won't see it, but the computer will when using ImageData:getPixel to lookup the color of the pixel below the mouse. This is much simpler and also measurably faster than using any other method I suggested.
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine

postalrat
Prole
Posts: 1
Joined: Mon Apr 12, 2010 10:49 pm

Re: Checking for mouse over irregular shapes

Post by postalrat » Mon Apr 12, 2010 10:54 pm

I wouldn't consider that method a hack. It's actually quite common. If you don't want to color the displayed image you could use a second image to map mouse clicks to areas.

This method also makes it real easy to create new maps or edit existing ones.

User avatar
nevon
Commander of the Circuloids
Posts: 938
Joined: Thu Feb 14, 2008 8:25 pm
Location: Stockholm, Sweden
Contact:

Re: Checking for mouse over irregular shapes

Post by nevon » Sat Jul 31, 2010 3:46 pm

I'm happy to report that I now comprehend vrld's method. It only took me 4 months to figure out.

Go me! :3

Post Reply

Who is online

Users browsing this forum: No registered users and 32 guests