Robert Voigtländer wrote:
>
>> On Tue, Jan 21, 2014 at 03:17:43AM -0800, Robert Voigtl�nder wrote:
>>
>
>> > I have objects like this:
>>
>> >
>>
>> > class Node(object):
>>
>> > def __init__(self, pos, parent, g , h):
>>
>> > self.pos = pos
>>
>> > self.parent = parent
>>
>> > self.g = g
>>
>> > self.h = h
>>
>> > self.f = g+h
>>
>> >
>>
>> >
>>
>> > I need to build a "list" of these objects. The amount is unknown.
>>
>> > On this list I need to regularly
>>
>> >
>>
>> > 1. check if a specific item - identified by Node.pos - is in the list.
>>
>> > 2. find the object with the lowest Node.f attribute and update or
>> > remove it
>>
>
>
> First thanks to all who responded. Although I only partially understand
> your answers as I am a Python starter. What's clear to me is the
> difference between object and instance of an object. Just didn't explain
> it well.
>
> Maybe I give some more info on what I need / want to do. I will also
> provide a working code example. Should have done this before.
>
> I would very much appreciate a working example of what you mean. Then I
> have a chance to understand it. :-)
>
> I would like to implement a class for a A* pathfinding algorithm. (there
> are ready libraries out there but I would like to learn it myself) This
> requires to maintain a list of nodes to be processed and nodes already
> processed. For new nodes I need to check if they are on one of the lists.
> I also need to regularly pick the node with the lowest value f from the
> list.
>
> Here some working code. For one function I sill need a solution. Any
> better solution is welcome.
>
> Thanks
> Robert
>
> ---------------
> class Node:
> def __init__(self, pos, parent, g , h):
> self.pos = pos
> self.parent = parent
> self.g = g
> self.h = h
> self.f = g+h
>
>
> def isinlist(nodeToSeatch):
> for item in openlist:
> if item.pos == nodeToSeatch: return True
> return False
>
>
> def lowestF():
> lowestF = ''
> for item in openlist:
> if item.f < lowestF: lowestF = item
> return lowestF
def lowestF():
return min(openlist, key=operator.attrgetter("f"))
> def deleteItemWithPos(pos):
> ## need this function or different approach
> pass
>
> openlist=[]
> openlist.append(Node((1,1),None,1,5))
> openlist.append(Node((1,2),(1,1),4,6))
> openlist.append(Node((1,3),(1,2),9,10))
>
> for item in openlist: print item.pos, item.f
>
> print isinlist((1,1))
> print isinlist((1,5))
>
> nextNode = lowestF()
> print nextNode.pos, nextNode.f
Here is an OO implementation of Chris Angelico's suggestion:
import heapq
class Node:
def __init__(self, pos, parent, g , h):
self.pos = pos
self.parent = parent
self.g = g
self.h = h
self.f = g+h
def __str__(self):
return "Node(pos={!r}, f={!r})".format(self.pos, self.f)
class Nodes():
def __init__(self):
self.lookup = {}
self.heap = []
def add(self, node):
self.lookup[node.pos] = node
heapq.heappush(self.heap, (node.f, node))
def __iter__(self):
return iter(self.lookup.values())
def __contains__(self, pos):
return pos in self.lookup
def lowest(self):
return self.heap[0][1]
def pop(self):
f, node = heapq.heappop()
del lookup[node.pos]
return node
nodes = Nodes()
nodes.add(Node((1,1), None, 1, 5))
nodes.add(Node((1,2), (1,1), 4, 6))
nodes.add(Node((1,3), (1,2), 9, 10))
for node in nodes:
print(node)
print((1,1) in nodes)
print((1,5) in nodes)
print(nodes.lowest())
--
https://mail.python.org/mailman/listinfo/python-list
