Python Forum

I am looking for the name of an algorithm if one exists, or something to read as an answer to this question.
I am writing a video game and I need to keep all background processes to a minimum so I am looking for a method of solving this goal that is as optimized as possible.

I have list of lists that forms a 2D grid of numbers like this

Output:
3, 4, 4, 5, 4, 4
5, 2, 2, 3, 3, 4 
3, 4, 4, 4, 4, 3 
4, 3, 4, 2, 2, 4 
5, 4, 5, 5, 3, 3 
5, 2, 5, 5, 2, 2 
5, 3, 5, 3, 4, 2 
5, 4, 3, 3, 4, 2 

I need to find every combination of neighbors in groups of 2 and in groups of 3.
The tile must be touching on the top, bottom, left, or right. Diagonals do not touch.
So there are 5 shapes, horizontal 2, horizontal 3, vertical 2, vertical 3, and elbow bend 3.
The final result should be a list of lists containing 2 or 3 values each.

Is there an algorithm or search pattern already designed that will minimize the amount of processing necessary create a complete output list?

What kind of game is it? Is that for a tile map?

(Dec-16-2019, 08:25 PM)Clunk_Head Wrote: [ -> ]The final result should be a list of lists containing 2 or 3 values each.

What are these values supposed to be, relative x,y? I don't know that anyone can understand from what you have here.

Can you post code for what your input "list of lists" and an example of what you want to come out of it?

(Dec-16-2019, 08:57 PM)michael1789 Wrote: [ -> ]What kind of game is it? Is that for a tile map?

What are these values supposed to be, relative x,y? I don't know that anyone can understand from what you have here.

(Dec-16-2019, 08:25 PM)Clunk_Head Wrote: [ -> ]I need to find every combination of neighbors in groups of 2 and in groups of 3.
The tile must be touching on the top, bottom, left, or right. Diagonals do not touch.
So there are 5 shapes, horizontal 2, horizontal 3, vertical 2, vertical 3, and elbow bend 3.
The final result should be a list of lists containing 2 or 3 values each.

These are the rules that define the groupings in the list.
The grid is simply a grid of numbers, from which I need to extract every grouping of neighbors according to the rules that I explained. They're really not that ambiguous.
The purpose of the numbers will have absolutely no effect on the algorithm used to group them.

(Dec-16-2019, 08:57 PM)michael1789 Wrote: [ -> ]Can you post code for what your input "list of lists" and an example of what you want to come out of it?

Output:
1, 2, 3
4, 5, 6
7, 8, 9

will produce

Output:
[
[1, 2], # horizontal 2
[2, 3], # horizontal 2
[1, 2, 3], # horizontal 3
[4, 5], # horizontal 2
[5, 6], # horizontal 2
[4, 5, 6], # horizontal 3
[7, 8], # horizontal 2
[8, 9], # horizontal 2
[7, 8, 9], # horizontal 3
[1, 4], # vertical 2
[4, 7], # vertical 2
[1, 4, 7], # vertical 3
[2, 5], # vertical 2
[5, 8], # vertical 2
[2, 5, 8], # vertical 3
[3, 6], # vertical 2
[6, 9], # vertical 2
[3, 6, 9], # vertical 3
[1, 2, 5], # elbow bend 3
[1, 2, 4], # elbow bend 3
[2, 3, 5], # elbow bend 3
[2, 3, 6], # elbow bend 3
[4, 5, 1], # elbow bend 3
[4, 5, 2], # elbow bend 3
[5, 6, 2], # elbow bend 3
[5, 6, 3], # elbow bend 3
[4, 5, 7], # elbow bend 3
[4, 5, 8], # elbow bend 3
[5, 6, 8], # elbow bend 3
[5, 6, 9], # elbow bend 3
[7, 8, 4], # elbow bend 3
[7, 8, 5], # elbow bend 3
[8, 9, 5], # elbow bend 3
[8, 9, 6] # elbow bend 3
]

This sounds almost like the beginning steps in some path finding algorithms but with very short paths. That might be a place to start searching. Try a search for A* (A-Star).
Algorithms to break 2D/3D grids apart into specifically shaped pieces also sound like something that is too useful not to have been done before but I didn't find anything that exactly matches your 'Tetris' shape finder.
I'm sure making it efficient when the grid gets large will be a challenge. If I can think of anything else I'll post back...

(Dec-16-2019, 09:45 PM)Marbelous Wrote: [ -> ]This sounds almost like the beginning steps in some path finding algorithms but with very short paths. That might be a place to start searching. Try a search for A* (A-Star).
Algorithms to break 2D/3D grids apart into specifically shaped pieces also sound like something that is too useful not to have been done before but I didn't find anything that exactly matches your 'Tetris' shape finder.
I'm sure making it efficient when the grid gets large will be a challenge. If I can think of anything else I'll post back...

I agree that's it's too important not to have been done before.
I will start looking for path finding algorithms (short). Thank you for the good tip.

I look forward to anything else that you come up with.

Does the size of your array change? If not, I would not worry too much about the algorithm. Figure out the groups once at the start of the game. Store all of the groups as lists of the indexes to those items. Then just pull those indexes each turn as you need them:

group_values = []
for group in groups:
    group_values.append(tuple(grid[x][y] for x, y in group))

That way you are not calculating at all in between turns, you are just pulling data. Also, you don't need to worry as much about the speed of the group finding algorithm, as long as it isn't slow enough to cause a notable pause at the start of the game.

If you can access numpy, you could possibly speed this up with integer array indexing. But I'm assuming you wouldn't have that for a game.

(Dec-16-2019, 10:18 PM)ichabod801 Wrote: [ -> ]Does the size of your array change?

Yes, the contents of the array change after every turn is taken. Values can be removed from any position in any column. The size changes every 6-13 turns. The entire thing needs to be recalculated after each turn otherwise impossible situations may arise.

(Dec-16-2019, 10:18 PM)ichabod801 Wrote: [ -> ]If you can access numpy, you could possibly speed this up with integer array indexing. But I'm assuming you wouldn't have that for a game.

No numpy, you are correct in that assumption.

Since it fires off every turn it's important that is be as fast as possible.

I am thinking that the top row, bottom row, leftmost column, and rightmost column are going to be the edge cases, literally, and that all other rows and columns will be able to follow a single algorithm.

Also, it's much more about the practice than the module as I may port this to other languages as I plan on writing this game for android too.

I was hoping for your input, specifically, on this. Please let me know if my answers bring anything else to mind.

For a fast algorithm, I would try numpy indexing and reshaping, something similar to this

import numpy as np

# arrays of indices prepared
h2 = np.array([0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 7, 8])
v2 = np.array([0, 3, 1, 4, 2, 5, 3, 6, 4, 7, 5, 8])
t3 = np.array([
    0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 3, 6, 1, 4, 7, 2, 5, 8,
    0, 1, 4, 1, 0, 3, 1, 2, 5, 2, 1, 4,
    3, 4, 7, 4, 3, 6, 4, 5, 8, 5, 4, 7,
    0, 3, 4, 3, 4, 1, 1, 4, 5, 4, 5, 2,
    3, 6, 7, 6, 7, 4, 4, 7, 8, 7, 8, 5])

# data array
x = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9])

# extract the tiles through indexing and reshaping
print(x[h2].reshape(6, 2))
print(x[v2].reshape(6, 2))
print(x[t3].reshape(22, 3))

Output:
[[1 2]
 [2 3]
 [4 5]
 [5 6]
 [7 8]
 [8 9]]
[[1 4]
 [2 5]
 [3 6]
 [4 7]
 [5 8]
 [6 9]]
[[1 2 3]
 [4 5 6]
 [7 8 9]
 [1 4 7]
 [2 5 8]
 [3 6 9]
 [1 2 5]
 [2 1 4]
 [2 3 6]
 [3 2 5]
 [4 5 8]
 [5 4 7]
 [5 6 9]
 [6 5 8]
 [1 4 5]
 [4 5 2]
 [2 5 6]
 [5 6 3]
 [4 7 8]
 [7 8 5]
 [5 8 9]
 [8 9 6]]

If you cannot use numpy, you could simulate this indexing on python lists.

(Dec-16-2019, 10:49 PM)Gribouillis Wrote: [ -> ]For a fast algorithm, I would try numpy indexing and reshaping, something similar to this

import numpy as np

# arrays of indices prepared
h2 = np.array([0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 7, 8])
v2 = np.array([0, 3, 1, 4, 2, 5, 3, 6, 4, 7, 5, 8])
t3 = np.array([
    0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 3, 6, 1, 4, 7, 2, 5, 8,
    0, 1, 4, 1, 0, 3, 1, 2, 5, 2, 1, 4,
    3, 4, 7, 4, 3, 6, 4, 5, 8, 5, 4, 7,
    0, 3, 4, 3, 4, 1, 1, 4, 5, 4, 5, 2,
    3, 6, 7, 6, 7, 4, 4, 7, 8, 7, 8, 5])

# data array
x = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9])

# extract the tiles through indexing and reshaping
print(x[h2].reshape(6, 2))
print(x[v2].reshape(6, 2))
print(x[t3].reshape(22, 3))

Output:
[[1 2]
 [2 3]
 [4 5]
 [5 6]
 [7 8]
 [8 9]]
[[1 4]
 [2 5]
 [3 6]
 [4 7]
 [5 8]
 [6 9]]
[[1 2 3]
 [4 5 6]
 [7 8 9]
 [1 4 7]
 [2 5 8]
 [3 6 9]
 [1 2 5]
 [2 1 4]
 [2 3 6]
 [3 2 5]
 [4 5 8]
 [5 4 7]
 [5 6 9]
 [6 5 8]
 [1 4 5]
 [4 5 2]
 [2 5 6]
 [5 6 3]
 [4 7 8]
 [7 8 5]
 [5 8 9]
 [8 9 6]]

If you cannot use numpy, you could simulate this indexing on python lists.

No, numpy. Also, the grid shrinks regularly which I failed to mention until my last reply.
The answer I'm looking for is algorithmic theory, not module base, please.
I can design it but I'm sure someone else has already invented that wheel.

(Dec-16-2019, 11:15 PM)Clunk_Head Wrote: [ -> ]the grid shrinks regularly

If it's shrinking, you can still use my solution. You calculate it once, and you have the list of indexes. When it shrinks, you can easily go through the list of indexes and throw out any that are invalid (that contain cells no longer in the grid).