طريقة بيثون وفعالة لإيجاد الخلايا المجاورة في الشبكة

Question

أقوم ببناء تطبيق قائم على البلاط في Python باستخدام Pyglet/OpenGL حيث سأحتاج إلى العثور على جميع الخلايا المجاورة لخلية معينة. أنا أعمل في ربع واحد من شبكة الديكارتية. كل خلية لها قيمة x و y تشير إلى وضعها في الشبكة (x_coord و y_coord). هذه ليست قيم البكسل ، بالأحرى مواقف الشبكة. أنا أبحث عن طريقة فعالة للحصول على الخلايا المجاورة. في Max ، هناك ثماني خلايا مجاورة ممكنة ، ولكن بسبب حدود الشبكة ، قد يكون هناك عدد أقل من 3. رمز زائف لنهج بسيط ولكنه غير فعال على الأرجح يبدو مثل هذا:

def get_adjacent_cells( self, cell ):
     result = []
     x_coord = cell.x_coord
     y_coord = cell.y_coord
     for c in grid.cells:
          if c.x_coord == x_coord and c.y_coord == y_coord: # right
               result.append( c )
          if c.x_coord == x_coord - 1 and c.y_coord == y_coord + 1: # lower right
               result.append( c )
          if c.x_coord == x_coord - 1 and c.y_coord == y_coord: # below
               result.append( c )
          if c.x_coord == x_coord - 1 and c.y_coord == y_coord - 1: lower left
               result.append( c )
          if c.x_coord == x_coord and c.y_coord == y_coord - 1: right
               result.append( c )
          // -- similar conditional for remaining cells

من المحتمل أن يعمل هذا بشكل جيد ، على الرغم من أنه من المحتمل أن يحتاج هذا الرمز إلى تشغيل كل إطار وفي شبكة أكبر قد يؤثر على الأداء. أي أفكار لنهج أكثر انسيابيا وأقل وحدة المعالجة المركزية؟ أو ، هل يجب أن أتعامل مع هذا النهج؟

شكرا لك مقدما.

Answer 1

لم يكن من الواضح بالنسبة لي ما إذا كانت هناك معلومات أخرى في الخلايا فقط من الإحداثيات X و Y. في أي حال ، أعتقد أن هناك حاجة إلى تغيير في هياكل البيانات لجعل هذا أسرع.

افترضت أن هناك معلومات إضافية في الخلايا وصنعت grid.cells كقامعة مع مفاتيح كونها tuples من الإحداثيات. يمكن القيام بشيء مماثل معgrid.cells كمجموعة إذا كان هناك فقط معلومات الإحداثيات في الخلايا.

def get_adjacent_cells( self, x_coord, y_coord ):
    result = {}
    for x,y in [(x_coord+i,y_coord+j) for i in (-1,0,1) for j in (-1,0,1) if i != 0 or j != 0]:
        if (x,y) in grid.cells:
            result[(x,y)] = grid.cells[(x,y)]

اعتمادًا على ما تريد القيام به بالبيانات ، قد لا ترغب في تحقيق نتائج ، ولكن نأمل أن تحصل على الفكرة. يجب أن يكون هذا أسرع بكثير من الكود الخاص بك لأن الكود الخاص بك يقوم بإنشاء 8 شيكات على كل خلية في grid.cells.

Answer 2

سيكون الكود الخاص بك بطيئًا بقدر حجم الشبكات الخاصة بك ، لأنك تكرر الخلايا فقط للحصول على 8 منها (التي تعرفها بالفعل إحداثياتها).

إذا تمكنت من القيام بوصول عشوائي من خلال مؤشراتهم ، أقترح شيئًا مثل ما يلي:

adjacency = [(i,j) for i in (-1,0,1) for j in (-1,0,1) if not (i == j == 0)] #the adjacency matrix

def get_adjacent_cells( self, cell ):
     x_coord = cell.x_coord
     y_coord = cell.y_coord
     for dx, dy in adjacency:
          if 0 <= (x_coord + dx) < max_x and 0 <= y_coord + dy < max_y: #boundaries check
#yielding is usually faster than constructing a list and returning it if you're just using it once
              yield grid[x_coord + dx, y_coord + dy]

max_x و max_y من المفترض أن يكون حجم الشبكة ، و grid.__getitem__ من المفترض أن يقبل توب مع الإحداثيات وإعادة الخلية في هذا الموقف.

Answer 3

حسنًا ، لن يساعد هذا في الأداء ، ولكن يمكنك تجنب تكرار الكود بالقول

if abs(c.x_coord - x_coord) == 1 or abs(c.y_coord - y_coord) == 1:
    result.append(c)

للتأثير على الأداء ، يجب أن تعرف خلايا الشبكة الخاصة بك من هم جيرانهم ، إما من خلال سمة مثل c.neighbors, ، أو من خلال بنية ضمنية ، مثل قائمة القوائم ، حتى تتمكن من الوصول عن طريق الإحداثيات.

grid = [[a,b,c],
        [d,e,f],
        [g,h,i]]

ثم يمكنك التحقق من الجوار باستخدام مؤشرات القائمة.

Answer 4

ربما تكون هذه هي الطريقة الأكثر فعالية للبحث عن الجيران إذا تم تنفيذ Grid.cells كمجموعة (على الرغم من أن هناك خطأ في أول مجموعة - تحتاج إلى اختبار المساواة مع X_Coord + 1 بدلاً من x_coord).

ومع ذلك ، فإن تنفيذ Grid.cells كقائمة من القوائم سوف تسمح لك بالإشارة إلى الخلايا الفردية حسب الصف ورقم العمود. سيسمح لك أيضًا بقياس العدد الإجمالي للصفوف والأعمدة. يمكن لـ get_adjacent_cells العمل أولاً عن طريق التحقق أولاً من الحواف الخلية الحالية ، ثم البحث عن الجيران في جميع الاتجاهات الأخرى وإلحاقها بقائمة النتائج.

Answer 5

في الشبكة ، يعني المجاور أنك تحتاج إلى خطوة واحدة فقط من التنسيق للوصول إلى الآخر إذا لم أكن عن طريق الخطأ أو مرتفع.

 if abs(c.x_coord -_coord +c.y_coord-y_coord) == 1
     print "they are adjacent!"

Answer 6

هذا يعمل مع صفائف Numpy

def get_adjacent_cells(arr, selected_idxs):
    """
    >>> arr = np.ones((3,))
    >>> get_adjacent_cells(arr, {(1,)})
    {(0,), (1,), (2,)}
    >>> arr = np.ones((3,2))
    >>> get_adjacent_cells(arr, {(1,1)})
    {(0, 1), (1, 0), (1, 1), (2, 1)}
    >>> arr = np.ones((3,2,3))
    >>> {(0, 1, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (2, 1, 0)}
    >>> arr = np.ones((3,2,3))
    >>> get_adjacent_cells(arr, {(1,1,0), (0,1,0)})
    {(0, 0, 0), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 1, 0), (1, 1, 1), (2, 1, 0)}
    """
    w = np.asarray(list(selected_idxs))
    new_idxs = []
    for col in range(w.shape[1]):
        w_ = w.copy()
        w_[:,col] += 1
        new_idxs.extend(list(w_))
        w_ = w.copy()
        w_[:,col] -= 1
        new_idxs.extend(list(w_))

    new_idxs = np.array(new_idxs)

    # remove out of bounds coordinates
    for col, dim_size in enumerate(arr.shape):
        new_idxs = new_idxs[(new_idxs[:, col] >= 0) & (new_idxs[:, col] < dim_size)]

    return selected_idxs.union(map(tuple, new_idxs))