On Tue, Jan 21, 2014 at 05:38:34AM -0800, 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
The function above is incorrect. I think it should be:
def lowestF():
lowestF = ''
for item in openlist:
if item.f < lowestF:
lowestF = item.f # Note the .f here
return lowestF
>
> def deleteItemWithPos(pos):
> ## need this function or different approach
> pass
def deleteItemWithPos(pos):
for n, item in enumerate(openlist):
if item.pos == pos:
del openlist[n]
return
else:
raise RuntimeError('Not in the list!')
>
> 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
My first suggestion would be to use a dict instead of a list:
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(pos):
return pos in opendict
def lowestF():
return min(opendict.values(), key=lambda x: x.f)
def deleteItemWithPos(pos):
del opendict[pos]
nodes = [
Node((1,1),None,1,5),
Node((1,2),(1,1),4,6),
Node((1,3),(1,2),9,10),
]
opendict = {}
for node in nodes:
opendict[node.pos] = node
for item in opendict.values():
print item.pos, item.f
print isinlist((1,1))
print isinlist((1,5))
nextNode = lowestF()
print nextNode.pos, nextNode.f
The above is more efficient and simpler. It is still O(N) for the lowestF()
function. Changing data structure could make that more efficient.
Oscar
--
https://mail.python.org/mailman/listinfo/python-list
