How to check if two user-drawn (squiggly) lines intersect?

Question

I'm thinking of making an online version of the game Sprouts, possibly using the JavaScript web browser graphics library p5.js

You can read more about it but basically there are 2 players that draw lines with their mouse between points. The lines can be straight or curved in any way. One of the rules is that no 2 lines can cross.

I haven't started making the game yet, but planning it ahead, everything seems relatively simple to accomplish except for one problem:

When a user draws a line, I need to figure out if this line intersects with another line. However, since these lines aren't linear or exactly mathematical in any way I'm used to, there doesn't seem to be a simple mathematical way I can check for intersection.

How would I check if two such lines, given that I know the location of every pixel on the lines, cross?

I apologize for no code, I haven't yet started it. If you wish to include code in your answer, you can use psuedocode or any gui programming that you might be familiar with. However, I would prefer a purely hypothetical answer, since everything is at this stage.

Here are some ideas I have:

• For each pixel on the line, I could check if any of the other lines has a pixel of the same position, in which case they overlap. This seems inefficient, so the below point is something else I came up with that is more efficient but less rigid and reliable.
• Before drawing the line, If you make sure all the lines are one color, for every pixel on the line, you could check if this pixel is already colored in the same color as the color of the lines, using something like getPixel() If so, abort drawing the line. This solutions seems prone to many problems and a bit fragile.

These two solutions either trade efficiency for reliability or vice-versa. Are there any other solutions you know? Keep in mind this will run in a browser, so efficiency is important.

Answer 1

Keep in mind this will run in a browser, so efficiency is important.

You need to give yourself a better idea of what kind of "efficiency" is important to you and your users. Both approaches you outlined seem reasonable to me. I wouldn't assume that a solution is inefficient before you try it and measure its performance.

Taking a step back, in general you're going to need to store the lines in some kind of data structure. You said the lines are not mathematical, but you can break the lines down into individual line segments or points, which are mathematical. That could be an array of line segments, or a 2D array of boolean values, or a map of points, or a quadtree. There are many options. Then you need to check for collisions between those lines or points and the new lines or points added by the other player.

Another option to consider is decreasing the resolution of your input space. For example, maybe your game window is 500x500 pixels, but you really only need the game board to be 100x100 possible point positions. You could scale that 100x100 game board up so it's displayed at 500x500. This would improve the "efficiency" of whatever solution you come up with.

But again, I wouldn't worry about "efficiency" at this point. Either solution you mentioned seems fine. Get that working and then iterate on it if you notice a problem. Good luck.