Puzzle game logic question - path finding?

Development Programming & Scripting Blueprint
1

In my BluePrint game, I place words, which all need to overlap another word, and every single word needs to be linked up. For example in the image below the board can be split in two where the orange line is, and none of the words on the left link up with those on the right side, which would make it invalid.

I am assuming this is some form of path-finding algorithm type of issue. Any ideas how I might go about finding if every word is linked up? I can see there are some path finding plugins in the marketplace.

Any guidance is appreciated.

Cheers,
Max

2

I think there may be an easier way. Presumably each word has a reference ( in an array? ). If you also have an array of bools for ‘word is intersecting’, then the final test is just to see if this bool array has any false values in it.

3

Thanks for the reply. I have a 2d array with numbers that show they are intersecting, but the problem is every word is intersecting with at least one other word, but still they aren’t all connected, as per the image.

4

You’re right, lemme think…

5

If I had a suitable path finding algorithm that stops when the first path is found (rather than optimal path) then I could check one square of every word (typically about 20 words on the board) has a path to one square on every other word. Still it is a lot of checks and how much time will it take that can’t find a path and give up and report there is no path?

6

Your grid should know what tiles has a letter. So you might have a Set of grid coords, containing all the letters.
But you don’t know if those letters all form a connection. You can now select a random coord containing a letter and perform a flood fill. The fill can only flow to adjacent coords (horizontal and vertical) and only if that coord contains a letter. each valid coord is added to a Set. When the flood fill is finished, the flood Set == letters Set. if not, some words are not connected.
Just a hobbyists thoughts.

7

It has to check that every word has a connection to every other word. I’m just trying to think of a way of doing it that wont go into a black hole…

8

Yes, I like that, I think that’s the way forward…

9

That sounds a lot less expensive than checking every word against every other word, each being a path search, so over a 100 path searches most likely.

I will see if I can wrap my head around your method. Sounds doable. Many thanks to all the input.

Cheers,
Max

10

I got the flood fill method working within a day, it was pretty easy. I do it with a recursive approach, constantly calling floodfill inside floodfill.

I used the following code as my pseudo-code basically:

It finishes without any noticeable delay at all.

Thanks again.