确定网格上的允许移动

问题描述：

任何人都可以提出一个合适的方法来确定一个网格上允许的移动类似于下图中的网格。确定网格上的允许移动

grid layout

假设piece1在位置A1和piece2在位置C3，如何可以找出哪些方格是如果piece1可以移动（比如说）3个平方和piece2可以移动2容许动作？

我已经花了太多的时间开发基于文本MUDS看来，我只是不能让我的大脑采取下一步将如何，即使在最简单的情况下，潜在的可视化运动。

如果它的事项，我试图做到这一点在JavaScript，但要完全诚实的，我认为我的失败这里是未能妥善概念化 - 不是在语言理解是失败的。

更新 - 我添加了下面的响应发布后编写的第一轮代码。我想这可能是有用的人在类似情况如我看到的代码

这是草率的，而且只适用于放置在电路板至今一个项目，但至少check_allowable_moves()函数适用于这个初始运行。对于那些想知道为什么我要创建那些奇怪的字母数字对象而不仅仅是使用数字x轴和y轴的原因 - 这是因为HTML中的id不能以数字开头。事实上假装我可能使用数字开始ID帮助了解我所得到的奇妙答案所描述的功能和概念。

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 
<head> 
<meta http-equiv="Content-Type" content="application/xhtml+xml;utf-8"/> 

<title>Test page</title> 
<style> 

    #chessboard { clear: both; border:solid 1px black; height: 656px; 
        width:656px; /*width = 8*40 + 16 for border*/ } 
    #chessboard .row { overflow: auto; clear: both; } 
    #chessboard .row span { display: block; height: 80px; 
          width: 80px; float: left; 
          border:solid 1px black; } 
    .allowable { background: blue; } 
</style> 
<script type="text/javascript" src="http://www.google.com/jsapi"></script> 
<script type="text/javascript"> 
    google.load("jquery", "1.2.6"); 
    google.load("jqueryui", "1.5.3"); 
</script> 
<script type="text/javascript"> 
$(document).ready(function() { 
    (function() { 
    var global = this; 
    global.Map = function(container) { 
     function render_board() { 
     var max_rows = 8; 
     var cols = new Array('a','b', 'c', 'd', 'e', 'f', 'g', 'h'); 
     var jqMap = $('<div />'); 
     jqMap.attr('id', 'chessboard'); 
     var x=0; 
     for(x; x<max_rows; x++) { 
      var jqRow = $('<span />'); 
      jqRow.addClass('row'); 
      var i=0; 
      for(i; i<cols.length; i++) { 
       var jqCol = $('<span />'); 
       jqCol.attr('id', cols[i]+(x+1)); 
       jqCol.addClass(cols[i]); 
       jqRow.append(jqCol); 
      } 
      jqMap.append(jqRow); 
     } 
    $('#'+container).append(jqMap); 
    } 
    function add_piece(where, id) { 
    var jqPiece = $('<div>MY PIECE'+id+'</div>'); 
    var jqWhere = $('#'+where); 
    jqPiece.attr('id', 'piece-'+id); 
    jqPiece.addClass('army'); 
    jqPiece.draggable({cursor: 'move', 
           grid:[82, 82], 
           containment: '#chessboard', 
           revert: 'invalid', 
           stop: function(ev, ui) { 
           //console.log(ev.target.id); 
           } 
          }); 
    jqWhere.append(jqPiece); 
    check_allowable_moves(where); 
    } 
    function check_allowable_moves(location) { 
    var x_axis = { 'a':1,'b':2, 'c':3, 'd':4, 'e':5, 'f':6, 'g':7, 'h':8 }; 
    var x_axis_alpha = { 1:'a',2:'b', 3:'c', 4:'d', 5:'e', 6:'f', 7:'g', 8:'h' }; 
    $('.allowable').droppable("destroy"); 
    $('.allowable').removeClass('allowable'); 
    //get the x,y values of the piece just placed 
    var x = parseInt(x_axis[location[0]], 10); 
    var y = parseInt(location[1], 10); 
    var x_min = x-2; 
    var y_min = y-2; 
     for(x_min; x_min<=x+2; x_min++) { 
     for(y_min; y_min<=y+2; y_min++) { 
      var jqCell = $('#'+x_axis_alpha[x_min]+y_min) 
      jqCell.addClass('allowable'); 
      jqCell.droppable({ accept: '.army', 
       drop: function(ev, ui) { 
       //console.log(ev, ui, $(this)); 
       //handle_drop(ev, ui, $(this)); 
       check_allowable_moves($(this).attr('id')); 
       } 
      }); 
     } 
     y_min = parseFloat(y)-2; 
     } 
    } 
    render_board(); 
    add_piece('d5', '2'); 
    } 
})(); 
var map = new Map('content'); 
}); 
</script> 
</head> 

<body id="debug"> 
    <div id="page"> 
     <div id="content"> </div> 
    </div><!-- end page --> 
</body> 
</html>

该图像没有进入您的文章。 – 2009-02-03 18:39:31

图像在那里，只是没有显示。以下是网址：http://farm4.static.flickr.com/3534/3250436085_c91b07c7fd.jpg?v=0 – 2009-02-03 18:42:37

已修复，由于某些原因，降价预览接受带有？的网址，但不包含实际呈现的帖子。如果还没有，请提交uservoice错误报告。 – 2009-02-03 18:43:30

答

假设件p位于位置x，y并且可以移动n个方块到位置x2，y2。这意味着（x - x2）和（y - y2）之间绝对差值的总和不能大于n。

如果你要显示哪些方块可以移动到（而不是采取输入X2和Y2），我觉得这是最好的循环遍历各地的一块正方形的所有位置。这是...

for (x - n TO x + n): 
    for (y - n TO x + n): 
     if (abs(x - x2) + abs(y - y2) <= n): 
      mark as okay.

这个答案假设件只能移动到相邻的方块，而不是对角。

编辑：如果你想要对角线移动，沿对角线移动的成本与水平或垂直移动一样多，那么问题实际上要容易得多 - 片段p可以在（x-n，x + n）和（y-n，y + n）。

答案如果斜向移动不花费多达水平+垂直移动（例如，如果对角成本1.5，而H/V成本1）变得复杂得多。

答

这纯粹是一个概念层面，但尝试这样的逻辑：

采取一切可能的位置一步之遥，从您的出发点，并把它们放在栈上（移至采取= 0）
弹出一个出栈和重复，使用新的坐标作为新的起点。（移动采取= 1）。你必须确保你不会把任何重复的坐标放在堆栈上
重复2直到你用尽了所有可用的棋子。

我可能无法很好地解释这，让我知道，如果你有什么我想说的任何问题。

答

你可以使用上面的方法，但使用递归。

递归“深度”是移动距离。

当深度>移动时折断。

每次迭代应该返回一个空间矢量并添加自己的位置。

删除重复

答

一般来说这些问题涉及的地方人能够达到一个相当有限的网格。采用网格大小的数据结构，其元素可以足够精确地保存剩余移动点的数量。

将网格初始化为未访问值。这不能在零到最大可能的移动速度范围内。负值是理想的。

将起始位置初始化为剩余移动次数。

此时有三种可能的方法：

1）重新扫描整个网格中的每个步骤。简单但较慢。终止是当没有点产生合法的举动。

2）将点存储在堆栈中。比＃1更快，但仍不是最好的。终止是堆栈空的时候。

3）将点存储在队列中。这是最好的。终止是当队列为空时。

Repeat 
    ObtainPoint {From queue, stack or brute force} 
    For Each Neighbor do 
     Remaining = Current - MovementCost 
     If Remaining > CurrentValue[Neighbor] then 
     CurrentValue[Neighbor] = Remaining 
     Push or Queue Neighbor 
Until Done

请注意，使用基于堆栈的方法，您总是会遇到一些情况，最终抛弃旧计算并重新执行它们。只有在遇到恶劣的地形比通过它便宜的情况下，基于队列的方法才会发生这种情况。

仅在循环结束时检查终止条件，否则在ObtainPoint尝试使用空队列或堆栈时终止。 ObtainPoint后空队列/堆栈不是意味着你完成了！

（请注意，伊恩的回答是一个相当大的扩展。）

确定网格上的允许移动

相关推荐