Certain seeds cause dungeon generation to get stuck in an infinite loop

[kpyrkosz]

Operating System

Linux x64

DevilutionX version

1.4.1 (latest release)

Describe

Some seeds, such as the 3 in the attached test case cause the program to hang during dungeon generation. I've attached a test case demonstrating the issue.

To Reproduce

TEST(Drlg_l2, seeds_stuck_in_an_infinite_loop)
{
        leveltype = GetLevelType(5);
        int bad_seeds[3] = { 606, 5248, 1054405 };

        for (int i = 0; i < 3; ++i) {
                pMegaTiles = std::make_unique<MegaTile[]>(GetTileCount(leveltype));
                CreateDungeon(bad_seeds[i], ENTRY_MAIN);
        }
}

Expected Behavior

Program does not hang

Additional context

No response

[StephenCWills]

As was mentioned in Discord, you can also reproduce using debug commands in a Multiplayer game.

restart 5 606
changelevel 5

And it was confirmed to hang in vanilla Diablo as well.

[AJenbo]

The issue here is that it fails to connect two doors, walking in the opposite direction, hitting a wall and not turning around.

beginning 22x10, end 10x12, dir: 3

                                         
                                         
                                         
                                         
                                         
                                         
                                         
                                 C##E    
                         C###E   #..#    
             C#####E     #...#   #..#    
            ,D.....#     #...#   #..#    
             #.....#     #...#   B##A    
             #.....#     #...#           
             #.....#     #...#           
             B##D##A     #...#           
               ,,,       B###A           
               ,,,                       
               ,,,     C#######E         
               ,,,     #.......#         
               ,,,     #.......#         
               ,,,     #.......#         
       C###E   ,,,     B#######A         
       #...D   CDE                       
       #...#   #.#                       
       #...#   #.#                       
       B###A   #.#         C#######E     
               #.#         #.......#     
               BDA         #.......#     
                ,          #.......#     
               ,,,         #.......#     
                ,          #.......#     
            C###D####E     #.......#     
            #........#     #.......#     
      C###E #........#     #.......#     
      #...# #........#     B#######A     
      #...# #........#                   
      #...# #........#                   
      B###A #........#                   
            B########A                   
                                         

After 1600 iterations:

                                         
                                         
                                         
                                         
                                         
                                         
                                         
                                 C##E    
                         C###E   #..#    
             C#####E     #...#   #..#    
            ,D.....#     #...#   #..#    
             #.....#     #...#   B##A    
             #.....#     #...#           
             #.....#     #...#           
             B##D##A     #...#           
               ,,,       B###A           
               ,,,                       
               ,,,     C#######E         
               ,,,     #.......#         
               ,,,     #.......#         
               ,,,     #.......#         
       C###E   ,,,     B#######A         
       #...D,  CDE                       
       #...#,  #.#                       
       #...#,  #.#                       
       B###A,  #.#         C#######E     
            ,  #.#         #.......#     
            ,  BDA         #.......#     
            ,   ,          #.......#     
            ,  ,,,         #.......#     
            ,   ,          #.......#     
            C###D####E     #.......#     
            #........#     #.......#     
      C###E #........#     #.......#     
      #...# #........#     B#######A     
      #...# #........#                   
      #...# #........#                   
      B###A #........#                   
            B########A                   
                               

[AJenbo]

It's stuck moving left and right between 31x11 and 38x11.

So looks like it decided to plow though the C corner and get stuck inside that wall.

[MohitS05]

I suppose a solution can be to add a std::future call and add a timeout, incase we don't get generation within time we stop that thread and try to regenerate with a different seed. I am new to this codebase, if pointed to generation code I'll be happy to implement it.

[StephenCWills]

If you intend to time it out, you can avoid the thread management and use SDL_GetTicks(). However, a better solution might be to detect the conditions for the infinite loop and bail. I don't know if that's feasible.

[AJenbo]

I think it's doable

[alex-polosky]

... However, a better solution might be to detect the conditions for the infinite loop and bail. I don't know if that's feasible.

Isn't this the halting problem?

[StephenCWills]

No, a key component of the halting problem is highlighted in that first sentence on Wikipedia.

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever.

We would only need to determine what the conditions are for this particular loop to become infinite, not any arbitrary algorithm. Then we could hardcode an edge case or workaround for it.