洪水充満の再帰経路探索のための再帰

Question

私は1〜2週間しかプログラミングしていませんが、私はターンベースの戦略ゲームを作っています。私は、ターンの開始時にプレイヤーの移動可能範囲を示し、移動が行われるように更新したかったのです。私はまた、範囲攻撃、戦争霧、AIのための経路発見のための方法が必要でした。

狩猟を割り当てた後、私は洪水の例であるhttps://www.redblobgames.com/pathfinding/a-star/introduction.htmlに出くわし、それを模倣しようとしました。他のほとんどの例は難解なクラスとメソッドで謎だったので、最初から始めました。ここに私が思いついたのがあります。私は問題がどこにあるのか分かっていますが、それを修正する方法がわかりません。

DEF mob_cost_calc（）：

#toymatrix is a fictional map for testing 
toymatrix = [[column for column in range(20)]for row in range(20)] 


#move wieght is a fictional weighted map for testing 
move_weight = [ 
    [3,5,2,7,3, 3,6,4,2,2, 4,2,3,4,2, 3,4,4,5,2], 
    [7,6,4,9,8, 7,5,1,9,8, 7,8,6,5,4, 4,8,6,5,4], 
    [9,3,8,4,6, 5,1,9,8,4, 7,3,5,6,1, 1,8,4,8,1], 
    [1,9,3,7,4, 8,5,1,9,3, 8,4,0,0,7, 9,9,8,7,9], 
    [4,9,6,5,5, 2,6,4,9,4, 8,7,9,8,7, 3,4,2,9,8], 

    [7,5,3,8,9, 3,4,7,6,5, 1,7,6,4,6, 8,7,4,2,5], 
    [6,1,2,8,3, 4,6,1,8,7, 1,3,4,7,6, 1,3,8,7,4], 
    [3,4,8,2,7, 5,6,1,8,3, 4,7,6,1,3, 8,7,4,6,5], 
    [1,8,3,7,4, 5,0,2,9,8, 4,3,7,5,8, 3,4,7,1,2], 
    [7,3,4,6,5, 1,8,2,3,7, 0,5,6,9,8, 4,7,5,1,9], 

    [3,4,8,5,9, 2,7,3,4,6, 1,1,5,5,4, 1,1,8,7,2], 
    [4,6,0,8,3, 7,4,1,9,1, 8,7,4,1,1, 9,2,8,1,3], 
    [4,7,5,9,5, 8,1,3,4,2, 6,1,0,7,8, 1,3,6,4,1], 
    [8,7,5,6,1, 9,4,3,8,5, 1,9,1,3,8, 4,7,5,1,9], 
    [2,9,3,8,4, 7,5,2,9,3, 4,8,7,1,9, 1,8,6,6,4], 

    [5,7,8,1,5, 6,4,2,3,4, 4,9,3,7,5, 1,9,4,3,8], 
    [7,5,2,1,8, 7,3,4,6,7, 8,5,6,2,1, 3,4,8,9,4], 
    [5,7,4,9,3, 8,7,1,2,9, 8,7,3,4,5, 6,8,7,6,2], 
    [1,3,8,4,7, 5,6,1,8,7, 4,3,8,9,2, 3,2,4,5,9], 
    [8,7,7,2,3, 9,7,8,4,6, 1,5,4,1,7, 8,2,3,9,5] 
    ]   
#map attributes    
TILE_SIZE =50 


#initializing the matrix format appropriae to the given map size 
    #1. max_range_matrix is a map of zeroes to store movement potential 
    #2. mod_draw_matrix is for drawing reachable tiles on the screen 
    #3. playerpos is the player's mobility check start position 
    #4. mobility is a unit's movement attribute 
max_range_matrix = [ 20*[0] for row in range(20)] 
mob_draw_matrix = [ 20*[0] for row in range(20)] 
playerpos = [10,10] 
mobility = 6 
#adds map mobility value in a a radius around the player position on a map 
#of zeros 
#1.1 zeros are discarded as impassable and act as a floodfill range 
#note:to see this, run program and adjust window to line up the matrix. 
for row in range(20): 
    for column in range(20): 
     if abs(playerpos[0] - column) + abs(playerpos[1] - row) <=mobility: 
      max_range_matrix[row][column] = move_weight[row][column] 

#zeros flood fill origin to exclude from distance addition 
max_range_matrix[playerpos[1]][playerpos[0]] = 0 

#Initializing variable for flood fill recursion 
    #1. nodes i and j represents a floodfill + shape mapping the area 
    #2. the various check dicts swap data for flood fill recursion process 
    #3. nodeC starts at player position and cycles through old open checks 
    #4. close check stores processed checks for path efficiency calcs 
NODEj = ((0,-1),(0,1)) 
NODEi = ((1,0),(-1,0)) 
mob_newOpenCheck_dict = {} 
mob_oldOpenCheck_dict = {} 
mob_closedCheck_dict = {} 
nodec = playerpos 
new_openCheck_update_dict = {} 


counter = 0 
while True: 
    if nodec != playerpos: 
     for old_position, old_move_cost in mob_oldOpenCheck_dict.items(): 
      nodec = [old_position[0], old_position[1]] 
#checking mobility cost down ,left, up, right from current nodeC position. 
#1. nodes to shift mobility lookup in a cross patern 
#2. storing coordinate(xy) and cumulative mobility values in new 
#dictionary 
#3. if cross checks overlap, it stores the lower of the two travel cost 
#values 
      #note: i=y and j=x. Matrix[i][j] and Position(x,y) are reverse 
      for i in range(2): 
       for j in range(2): 
        i_adj = nodec[1] + NODEi[i][j] 
        j_adj = nodec[0] + NODEj[i][j] 
        current_move_cost = max_range_matrix[i_adj][j_adj] 
         + old_move_cost 

        current_position = (j_adj, i_adj) 

        #testing for lowest travel cost on current tile 
        #evaluation 
        #swaping dicts to prevent self editing durring recursion 

        #problem!!!!!!!!!!!!!!! 


        new_openCheck_update_dict = {} 

        for new_position, new_move_cost in 
        mob_newOpenCheck_dict.items(): 
         if current_position != new_position: 
          new_openCheck_update_dict[current_position] = 
          current_move_cost 
         elif current_position == new_position and 
          current_move_cost < new_move_cost: 
          new_openCheck_update_dict[current_position] = 
          current_move_cost 

        for current_position1, current_move_cost1 in 
        new_openCheck_update_dict.items(): 
         mob_newOpenCheck_dict[current_position1] = 
         current_move_cost1 





    else: 
     #checking mobility cost down ,left, up, right from player position. 
     #1. nodes shift mobility lookup in a cross patern 
     #2. storing coordinate(xy) and mobility value in new open dictionary 
     #note: i=y and j=x. Matrix[i][j] and Position(x,y) are reverse. 
     for i in range(2): 
      for j in range(2): 
       i_adj = nodec[1] + NODEi[i][j] 
       j_adj = nodec[0] + NODEj[i][j] 
       move_cost = max_range_matrix[i_adj][j_adj] 
       move_cost_pos = (j_adj, i_adj) 
       mob_newOpenCheck_dict[move_cost_pos] = move_cost  

    nodec = [0,0] 

    #removing impassable area(s) from floodfill scan 
     #note:cannot delete from interating object so a list is used 
     #and cleaned at every pass 
    del_zero_positions = []   
    for position, move_cost in mob_newOpenCheck_dict.items(): 
     if move_cost == 0: 
      del_zero_positions.append(position) 

    for position in del_zero_positions: 
     del mob_newOpenCheck_dict[position] 

    #dumping mobility old check into closed check 
    for position, mob_cost in mob_oldOpenCheck_dict.items(): 
     mob_closedCheck_dict[position] = mob_cost 

    #replaceing mobility old check with with new check data for next 
    #floodfill pass. 
    #compare with closed to make sure fronteir doesn't move backwards 


    #problem!!!!!!!!!!!!!!!!!! 


    mob_oldOpenCheck_dict = {} 
    new_openCheck_update_dict = {} 
    for new_position, new_move_cost in mob_newOpenCheck_dict.items(): 
     for closed_position, closed_move_cost in  
      mob_closedCheck_dict.items(): 
      if new_position != closed_position: 
       new_openCheck_update_dict[new_position] = new_move_cost 

    for key, value in new_openCheck_update_dict.items(): 
     mob_closedCheck_dict[key]=value 


    #clearing new check for next pass 
    mob_newOpenCheck_dict = {} 



    #set counter for experimentation 
    if counter == 2: 
     break 
    else: 
     counter += 1 
     continue 






print('map matrix') 
print(toymatrix) 
print('\nmax range_matrix') 
print(max_range_matrix) 
print('\nmob_newOpenCheck_dict') 
print(mob_newOpenCheck_dict) 
print('\nmob_oldOpenCheck_dict') 
print(mob_oldOpenCheck_dict) 
print('\nmob_closedCheck_dict') 
print(mob_closedCheck_dict) 

mob_cost_calc（）

Answer 1

が

で反復チェックを交換する場合mob_newOpenCheck_dictでcurrent_positionと current_move_cost < mob_newOpenCheck_dict [current_position]：あった