0

我正在创建一个小游戏，您需要在地图上移动部队。为了检测是否可以进行移动，我必须验证两个方格之间是否有路。因此，我递归地从一个方格开始，取四个方格（上、下、左、右），并在以下条件下递归地重复测试，因为我只得到死角或目标方格。所有的方块都必须在玩家的控制之下。

我的类案例中有我的递归代码实现：

public boolean isContiguJoueur(Case case_origine, Case case_destination, Case[] cases)  {
 boolean haut_true=false, droite_true=false, bas_true=false, gauche_true=false;
 // Above
 if(this.haut!=null)    {
  if(haut.joueur==this.joueur && this.haut!=case_origine)   {
   if(this.haut==case_destination)  {
    return true;
   }
   haut_true=haut.isContiguJoueur(this,case_destination, cases);
  }
 }
 // ...
 // Same code than Above, only variables names change
 // ...
 return haut_true||droite_true||bas_true||gauche_true;
}
  • 正方形的类名：Case
  • 地图数据：Case[] case
  • 玩家ID：joueur
  • 上例：haut

该代码在小地图（约 50 到 100 个方格）上运行良好。但我在更大的上得到了这个：

08-25 11:26:31.912: E/AndroidRuntime(5497): FATAL EXCEPTION: main
08-25 11:26:31.912: E/AndroidRuntime(5497): java.lang.StackOverflowError
08-25 11:26:31.912: E/AndroidRuntime(5497):     at mypackage.isContiguJoueur(Case.java:xxx)
... x 100

抱歉我的英语不好，感谢您以后的帮助！:-)

编辑：我忘了。为了避免大量无用的递归测试，我已经这样做了：

if(this.droite!=null && !haut_true) {
// ...
if(this.bas!=null && !haut_true && !droite_true)    {
// ...
if(this.gauche!=null && !haut_true && !droite_true && !bas_true)    {
// ...
4

2 回答 2

1

我只是在我的类案例中添加一个布尔值，如果我测试这个案例，我将布尔值设置为 true，我以后不会进来。改进很重要！在大约 n^4（n 是玩家拥有的案例数量）测试之前。现在大约是n。使用我最大的地图并且玩家拥有整个地图，我没有错误。

于 2012-08-26T16:36:27.863 回答
0

您的问题是您的路径与板上的正方形数量成指数关系。堆栈溢出错误意味着您递归太多次：每次递归都占用堆栈空间，而您正在用完它（Chaque 递归利用 l'espace sur le pile，et il y'en a trop，alors il nya plus d 'espace - et c'est une dépassement de pile）。

您可以迭代地执行此操作（无递归）而不会遇到此问题。但请记住，可能路径的数量仍然很大，这可能会消耗 CPU。

希望这可以帮助，

TG

于 2012-08-25T22:03:40.433 回答