C ++如何生成一个随机的路径 [英] C++ How to generate a random Path

问题描述

我试着写，可以生成一个随机的路径给定的分数二维数组（X，Y）的函数。

现在的路径有几个要求，我想它，以满足它是有效的。 路径的不能

• ...从点的 A 为 B
直线
• ...反悔本身，而是可以倒退（<​​EM>下面展示了的）。
• ...平行/沿本身。

我也想确保路径开始从左边结束在右边希望保持它的简单。

所以我在寻找的东西会做：

  ......... | ......... | ########。
......... | ......... | .......＃。
## ... ###结束| .... ####。 | ... #####。
。###### .. | ##### ..＃。 | ...＃.....
......... | ....... ##月底| ...＃＃＃＃＃＃ 结束
 

但我不知道从哪里开始这里面的变化，做一些类似的信息很少。

我可以去A *溃败，但似乎矫枉过正，从我知道的A *（变化不大的），我需要创建假的障碍。反正之前，我去一个咆哮，谁能帮助我？

任何建议，大大AP preciated！谢谢你。

解决方案

下面的描述和code段应提供足够的信息来解决问题，而不提供一个确切的解决方案。注：以下不能满足所有的标准（例如，preventing一条直线的解决方案），但任何遗漏的部分应该很容易填写

。

---

1. 创建网格
2. 生成随机起始细胞
3. 在生成随机的结局细胞比起始细胞
不同
4. 步行从小区出发到结束细胞
   1. 标记每个位置被参观
   2. 在确定该位置上的有效举措
      1. 在至少1个有效的举措：添加此位置的位置到解决途径，并更新这个位置成为有效的举措之一
      2. 在没有有效的举措：更新这个位置是最近加入到了解决途径的位置（即备份）以及最近删除的位置 加入到该溶液路径
         • 请注意，如果解路径为​​空再次重新启动在步骤4
5. 重置电网恢复到原来的状态
6. 遍历解决路径，并为参观标记每个细胞
7. 打印电网

---

  //第1步
格之格（10，10）;

//第2步
细胞开始= grid.generateRandomCell（）;

//第3步
小区边缘=启动;
而（完==开始）
{
    结束= grid.generateRandomCell（）;
}

的std ::矢量＆lt;电池＆gt; solutionPath;

//第4步
细胞POS =启动;
而（POS！=结束）
{
    //步骤4.1
    grid.setValue（POS，'＃'）;

    //步骤4.2
    的std ::矢量＆lt;电池＆gt; possibleMoves = getPossibleMoves（电网，POS）;
    如果（！possibleMoves.empty（））
    {
        //步骤4.2.1
        solutionPath.push_back（POS）;
        POS = possibleMoves [兰特（）％possibleMoves.size（）];
    }
    其他
    {
        //步骤4.2.2
        如果（！solutionPath.empty（））
        {
            POS = solutionPath.back（）;
            solutionPath.erase（ -  solutionPath.end（））;
        }
        其他
        {
            POS =启动;
            grid.reset（）;
        }
    }
}

//第5步
grid.reset（）;

//第6步
用于（为size_t i = 1; I＆LT; solutionPath.size（）; ++ I）
{
    grid.setValue（solutionPath [我]，'A'+（（I  -  1）％26））;
}
grid.setValue（开始，@）;
grid.setValue（年底，！）;

//第7步
性病::法院＆LT;＆LT;格＆LT;＆LT; \ N的;
 

I'm trying to write a function that can generate a random path for a given 2D array of points (x, y).

Now the path has a few requirements I'd like it to meet in order for it to be valid. The path cannot:

• ...be a straight line from point A to B.
• ...go back on itself but can go backwards (demonstrated below).
• ...run parallel/along itself.

I also want to make sure the path starts from the left and ends on the right to hopefully keep it simple.

So I'm looking for something that would do:

.........     | .........     | ########.
.........     | .........     | .......#.
##....### end | ....####.     | ...#####.
.######..     | #####..#.     | ...#.....
.........     | .......## end | ...###### end

But I don't know where to start and there's vary little information available that does something similar to this.

I could go the A* rout but that seems overkill and from what I know about A* (vary little) I'd need to create "fake" obstacles. Anyway before I go on a rant, can anyone help me?

Any suggestions is greatly appreciated! Thank you.

解决方案

The following description and code snippet should give you enough information to solve the problem without providing an exact solution. Note: the following does not satisfy all of your criteria (e.g., preventing a straight line solution) but any missing pieces should be easy to fill in.

---

1. Create the grid
2. Generate random starting cell
3. Generate random ending cell that is different than the starting cell
4. Walk from the starting cell to the ending cell
   1. Mark each position as being 'visited'
   2. Determine the valid moves from this position
      1. At least 1 valid move: add this position position to the 'solution path' and update this position to be one of the valid moves
      2. No valid moves: update this position to be the position most recently added to the solution path (i.e., backup) and remove the position most recently added to the solution path
         • Note if the 'solution path' is empty restart again at step 4

5. Reset the grid back to its original state
6. Traverse the solution path and mark each cell as 'visited'
7. Print grid

---

// Step 1
Grid grid(10, 10);

// Step 2
Cell start = grid.generateRandomCell();

// Step 3
Cell end = start;
while (end == start)
{
    end = grid.generateRandomCell();
}

std::vector<Cell> solutionPath;

// Step 4
Cell pos = start;
while (pos != end)
{
    // Step 4.1
    grid.setValue(pos, '#');

    // Step 4.2
    std::vector<Cell> possibleMoves = getPossibleMoves(grid, pos);
    if (!possibleMoves.empty())
    {
        // Step 4.2.1
        solutionPath.push_back(pos);
        pos = possibleMoves[rand() % possibleMoves.size()];
    }
    else
    {
        // Step 4.2.2
        if (!solutionPath.empty())
        {
            pos = solutionPath.back();
            solutionPath.erase(--solutionPath.end());
        }
        else
        {
            pos = start;
            grid.reset();
        }
    }
}

// Step 5
grid.reset();

// Step 6
for (size_t i = 1; i < solutionPath.size(); ++i)
{
    grid.setValue(solutionPath[i], 'A' + ((i - 1) % 26));
}
grid.setValue(start, '@');
grid.setValue(end, '!');

// Step 7
std::cout << grid << "\n";

这篇关于C ++如何生成一个随机的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！