New to Golang and Struggling with Pointers in A* Implementation

blov · · 258 次点击    
这是一个分享于 的资源,其中的信息可能已经有所发展或是发生改变。
<p>Hey everyone:</p> <p>I&#39;m a Javascript developer learning Go and am currently trying to implement A* as a maze solver.<a href="" rel="nofollow"> Here&#39;s</a> my first stab (input maze comes from <a href="" rel="nofollow">this</a> Daily Programmer challenge):</p> <p>It seems like I&#39;ve gotten the algorithm implementation correct, as I&#39;m finding the target node with various inputs, but I can&#39;t seem to get reconstructPath to work. I have a reallllly nagging hunch that this has to do with pointers/dereferencing/passing by reference vs passing by value in my assignment of cameFrom, but I can&#39;t for the life of me puzzle it out. For instance, the inputs:</p> <pre><code>start := maze.Nodes[1][1] end := maze.Nodes[1][3] path, _ := maze.FindPath(start, end) fmt.Println(path) </code></pre> <p>in my main goroutine output</p> <pre><code>[{1 3 0xc42000fa20 0 0 . &lt;nil&gt;}] </code></pre> <p>Can anyone spot the errors/problems in my approach? Thanks!</p> <hr/>**评论:**<br/><br/>binaryblade: <pre><p>Your edges field is a pointer to a slice which is not what you want, slices are inherently reference types. Did you mean to have a slice of node pointers?</p></pre>thestalkmore: <pre><p>I think you&#39;re the winner! Made modifications and all seems to be well.</p></pre>thestalkmore: <pre><p>I lied. Some paths get stuck in a loop.</p></pre>tmornini: <pre><p>Perhaps the correct solution is detecting the loop and bailing out?</p></pre>whizack: <pre><p>unless i&#39;m missing something, you never assigned any node to cameFrom in your structure before calling reconstructPath.</p></pre>thestalkmore: <pre><p>The gist I posted was from a different approach on accident. I&#39;ve updated it.</p></pre>whizack: <pre><pre><code>gScore := make(map[Node]float64) fScore := make(map[Node]float64) openSet := make(map[Node]Node) closedSet := make(map[Node]bool) </code></pre> <p>basically the hash of a user defined type isn&#39;t guaranteed to be deeply comparable. Dumping these maps will probably show a lot of errors in how the nodes are indexed.</p> <p>if your intent is to hash on their location, perhaps make a method for Node called Position() that returns the position as a unique value and map the key to position as a string instead of using the node itself.</p></pre>Redundancy_: <pre><p>It&#39;s failing to load the gist for me unfortunately. I might try again over the weekend.</p> <p>I really recommend that you start with unit tests for your basic data structure manipulations. I think that will help to a certain extent with catching things where you might be passing copies rather than references and other gotchas.</p></pre>Redundancy_: <pre><p>Unrelated to the bugs that you&#39;re seeing - </p> <p>The costs of your open and closed list manipulations are frequently big performance considerations in A<em>, and things like hashmaps may be worth avoiding by packing items into slices and referencing by the position in the slice. Note that using a slice of Node (rather than Node</em>) should also help by packing the Nodes into a contiguous block of memory giving potentially better cache behaviour.</p> <p>The topic of designing the Open list for an optimal balance of insert and pop behaviour is also a pretty big topic. There were some interesting options I remember seeing in AI Game Programming Wisdom to do with a partially sorted (n items) list. Finding the smallest item by going over a full map to find the smallest item each time may not be very optimal.</p></pre>

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

258 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传