Map Indexing

Monkey Forums/Monkey Programming/Map Indexing

FBEpyon

(Posted 2015) [#1]

Hello,

I was hoping some one would be able to answer this before I get home and try it out for myself, but in C# you can index dictionaries, but I wasn't sure if it was possible to do the same thing with Maps in monkey?

Thanks,

FBEpyon

Samah

(Posted 2015) [#2]

Do you mean like this?

myMap["foo"] = "bar"
Print myMap["foo"]

If so, no. You need to use the Get/Set methods.

myMap.Set("foo", "bar")
Print myMap.Get("foo")

FBEpyon

(Posted 2015) [#3]

Okay thanks for the replay, I was working on my game, and monkey's Map are so much better than the one provided in MAX, so I was moving code over to Monkey and then switching a lot my list based things to Maps in hopes that I could switch them over to Array format like you could with the list in Max..

Thanks,

FBEpyon

ImmutableOctet(SKNG)

(Posted 2015) [#4]

@FBEpyon: You can still technically use lists of a specific base-class, and then cast down from there. Any BlitzMax code using a 'TList' just uses dynamic casts anyway. Lists can also be used to convert to arrays. Just keep in mind that doing that with the standard containers is inefficient on some targets. Usually it's not needed, as you can just use enumerators ('Eachin' keyword). For the 'List' class, you can use 'ToArray'; not sure about 'Map', though. If all you want is to access specific indexes of a list, then you'll have to write your own system to count the nodes (Not very hard). The 'Stack' class may fit better for your needs in that case; it has 'Get' and 'Set' methods, and it automatically grows. It's not a perfect replacement for 'List' and 'TList', though. Your first assumption of using an 'IntMap' like an array can be inefficient, but it's not a bad choice. I have done this with my own projects, but that was about unique IDs in an object hierarchy.

I hope that clears up your options a bit better. Also, if you were using a statically (Or manually) managed array, then you can still do that in Monkey.

FBEpyon

(Posted 2015) [#5]

Yeah I have done all of what you were talking about, but I was hoping that Maps were more like dictionaries are in C#, but now looking at it in a bit more detail it looks like Maps are nothing like them. Well I guess back to list..

Samah

(Posted 2015) [#6]

@FBEpyon: Yeah I have done all of what you were talking about, but I was hoping that Maps were more like dictionaries are in C#, but now looking at it in a bit more detail it looks like Maps are nothing like them. Well I guess back to list..

Aren't they all just terms for the same thing? Map, dictionary, associative array, table...

ImmutableOctet(SKNG)

(Posted 2015) [#7]

Depends on semantics and application. Tables can be continuous portions of memory, where each element's representation (Key) is the offset in memory. This can be applied at the level of integers, so you end up with an integer array being called a table. This terminology is commonly used with hashing algorithms and the like, where you honestly don't need more to the table than two elements; the data itself, and the index of the array used to retrieve that information.

With linked lists, you don't deal with integers (Well, technically, you do), you deal with nodes. The node structure also means that technically, linked lists are node-maps. Linked lists also have the dynamic attribute of being independent of contiguous regions of memory (Theoretically). But then there's other types of tables, which are basically structure-arrays (Single entry, multiple elements). How you store a table is somewhat arbitrary, and Monkey's reference-only setup shows this. How you access a table is also arbitrary, but at a low level, it tends to be raw memory access.

Maps are traditional "dictionaries", though; they're an associative array of sorts. Monkey's standard 'Map' just restricts you from getting explicit positions or IDs (Other than actual nodes). That's because Monkey uses a node-based implementation, so besides memory addresses, the only way to get "offsets" (Like you could with an array) is to count. Monkey's maps are also auto-sorted by default, meaning there's an explicit cost to adding an element (Sorting, and potentially checking against the existing nodes). And then, to access a specific node by moving down the "links" (References/pointers) in the "tree". This is also costly, because modern "pipelined" processors (x64, at least) have to pre-fetch this into cache. The thing is, you get into a lot of problems when nodes are in different segments of memory. Basically, when a lot of objects are spread out into different portions of memory, it takes time to access and represent them in the CPU's cache. This is compared to contiguous storage, where everything can very clearly be loaded in one go, allowing the processor to just work off of what's in its L1 and L2 caches. There's pros and cons to this, but luckily, modern operating systems' heaps and garbage collectors try to keep memory "lined up". I've heard that C#'s standard GCs do this for lists, too. Also, keep in mind that 'Nodes' are small objects, so it's not like you'd be loading a lot from different places. Accessing the information "in" those nodes can be costly, though. The point I'm trying to make is that cache misses (Long pauses reading from memory) are huge time-sinks for very little benefit (Some hardware benefits from this by allowing another thread to run on the "waiting" core; that's something Intel's been working around). Arrays are just (Usually contiguous) portions of memory. Anyway, enough about the memory tangent; I honestly just wanted to go on a tangent about modern memory management.

The point is, use 'Lists' or 'Stacks' for normal storage, use 'Maps' for association (This can be done for "IDs"). And what is and isn't a table (Or map) can be a blurry line. So, FBEpyon, lists and stacks are the way to go. Only use maps if you need to represent the elements with unique IDs, but only if you have to. If it's about easily accessing elements, enumerators are your friends. If you're unsure, you can tell us more about your specific case.

FBEpyon

(Posted 2015) [#8]

Dictionaries are very different in C# from monkey, I have used them before with Unity3D and they don't require and abstract methods in order to work, and you can assign any object to the key and value. If we had access to proper Dictionaries then I would be able to complete my Path Finding for my program I have been working on with out the slow downs of using List or stacks to store the Paths.

Being able to use Dictionaries like arrays are nice because I can get the first object by doing distance[start] = 0where with monkey you have to make a Class that extends the standard Map<KEY,VALUE>, and then add in the Compare method to the class.


// Dictionary Example:
Dictionary<node, float> distance = New Dictionary<node, float>
Dictionary<node, node> previous = New Dictionary<node, node>

distance[start] = 0
previous[start] = Null

From what I have been playing with this is not possible with the current state of Maps in Monkey, if you have some sort of work around this would be great! Until then I will be limited to using List or Arrays themselves.


'Map Example:

Class distance<T> Extends map<Float, T>

         Method Compare:Int(key1:Int, key2:Int)

                     Return key1 - key2

         End

End

Local dist:distance<Node> = New distance<Node>

dist.Add(Node,0)

I'm not sure if this is even correct or not.. but that is a lot unneeded coding to get this to work. :(

Let me know if there is another option PLEASE!!

This is what I'm trying to recode..

http://www.blitzmax.com/Community/posts.php?topic=104231

Samah

(Posted 2015) [#9]

FBEpyon this is the exact reason I made DiddyStack/DiddyList/DiddySet, so that you don't need to extend the class for every type. Just implement IComparable in your key class and you're done. Alternatively, assign an IComparator to the stack to tell it how to sort. Pretty sure C# works the same way.
They extend the official Stack/List/Set classes and are interoperable with them in many places.

https://github.com/swoolcock/diddy/blob/master/src/diddy/containers.monkey
https://github.com/swoolcock/diddy/blob/master/src/diddy/diddystack.monkey

There is currently no "DiddyMap" class, but I could pretty easily implement it.

muddy_shoes

(Posted 2015) [#10]

The ability to use "any" datatype as a key in C# comes from the fact that its base Object provides Equals and GetHashCode implementations. Mark, for whatever reason, decided not to follow this design in Monkey. However that design doesn't free you entirely from the need to possibly override those implementations and his design doesn't stop you from achieving the same functionality as the C# design.

It's a bit hard to get past the fact that you say you just need to get this bit done to get your path-finding working well and then you post a snippet with a 5 line Compare implementation and declare it to be "a lot [of] unneeded coding". It may be a little tedious having to implement the method in situations where C# wouldn't require it but, considering Monkey's design, it's surely a very tiny amount of needed coding?

Anyway, I looked at the thread you linked and it just has some non-Monkey code declared as broken. Perhaps if you post your Monkey code people can give you specific help with what you need to do to use the Monkey maps (if you need to do so at all).

FBEpyon

(Posted 2015) [#11]

Hello,

Sorry about that, it was written in BlitzMax, here is the code converted to Monkey for the most part, I didn't add any of the drawing commands and things, but I figured you would get the idea from this..


Class MyApp Extends App

	Field player:Node
	Field target:Node

	Field map:Grid

	Method OnCreate:Int()

		SetUpdateRate(60)
		player = New Node(5,5)
		target = New Node(10,10)

		map:Grid = New Grid(16,16)
		map.Generate(player,target)

	End

	Method OnUpdate:Int()

	End

	Method OnRender:Int()

		Cls

		For n:Node = Eachin map.data

			SetColor 255,255,255

			If map.path.Contains(n)

				SetColor 255,0,0

			EndIf

			DrawRect n.x * 16, n.y * 16, 16, 16

		Next

	End

End

'Tile class for storying the information about the current tile in the map (ex: x,y,style,etc.)

Class Tile

	Field x:Int, y:Int

	Field g:Int, h:Int

	Field parent:Node

	Method New(_x:Int, _y:Int)

		x = x
		y = y
		g = 0
		h = 0

	End

	Method GetF:Int()

		Return g + h	

	End Method

End

'Grid is used to lay out the tiles and to assign a path based on the grids returning path list

Class Grid

	Field data:Tile[]

	Field width:Int, height:Int

	Field path:List<Node>

	Method New(_width:Int, _height:Int)

		data = new Tile[_width * _height]

		width = _width
		height = _height

		path = New List<Node>

		For Local x:Int = 0 Until width
		For Local y:Int = 0 Until height

			data[x + y * width] = New Tile(x,y)

		Next
		Next

	End

	Method Generate:Void(s:Tile, t:Tile)

		Local start:Tile = data[s.x, s.y]
		Local target:Tile = data[t.x, t.y]

		Local open:List<Tile> = New List<Node>
		Local clsd:List<Tile> = New List<Node>

		Local current:Tile = start

		open.AddLast(start)

		While Not open.IsEmpty()

			For Local v:Tile = EachIn open

				If v.GetF() < current.GetF() Or v.GetF() = current.GetF() And v.GetF() < current.H

					current = v

				EndIf

			Next

			open.Remove(current)
			clsd.AddLast(current)

			If current = target

				current = target
		
				While current <> s

					path.AddLast(current)
					current = current.parent			

				Wend

				path.Backwards()

				Exit

			End

			For n:Node = EachIn neighbour(current)

				If close.Contians(n)

					Continue

				End

				Local newg:Int = current.g + distance(current,n)

				If newg < n.g Or Not open.Contains(n)

					n.g = newg
					n.h = distance(n, target)
					n.parent = current

					If Not open.Contains(n)

						open.AddLast(n)

					End

				EndIf

			Next

		End

		Return

	End Method

	Method neighbour:List<Tile>(n:Tile)

		Local l:List<Tile> = New List<Tile>

		For Local x:Int = -1 To 1
		For Local y:Int = -1 To 1

			Local checkx:Int = n.x + x
			Local checky:Int = n.y + y

			If checkx >= 0 And checky >= 0 And checkx < width And checky < height

				l.AddLast(data[checkx + checky * width])

			End

		Next
		Next

		Return l

	End

End

Function Main:Int()

	New MyApp
	Return 0

End

Sorry I wasn't trying to make a statement that Monkey is broken, but I like to figure out thing with out using the most code possible, because there is always a way around something..

What I'm trying to do is path-finding for my game were you click on the dirt and then the goblin (or dwarf) will start digging.. I need to develop a path to the dirt or other objects that you are targeting. I was hoping to use Maps to help speed this up, but I'm reading on other post there isn't really a huge increase in speed other than HashTables..

Edit ** Replace Node Class w/ Tile to not confuse with the current Node classes.

Thanks,

muddy_shoes

(Posted 2015) [#12]

I was hoping for working code using Lists. It's very difficult to respond to broken code that you're editing in the post as I type. You just removed the Node definition, said you're replacing it with Tile but didn't add a Tile definition.

Can you just clarify where you would want to use Maps? Do you want to replace your open and closed lists with Maps keyed on Tiles/Nodes in order to speed up the "Contains" tests?

FBEpyon

(Posted 2015) [#13]

: muddy_shoes :
The code posted above has already corrected everything to get it to work, and I have also added in drawing functions that should work was well to show you the path being draw on the screen (if not sorry i'm at work)..

But yes I would like to replace the open/closed list with Maps to help increase the speed..

Thanks,

muddy_shoes

(Posted 2015) [#14]

Okay, I'm sure you'll discover later that the code is some distance from working or even compiling.

To answer the immediate question about how to use a map with your Tiles, all you'd need is something like:

Class TileMap<V> Extends Map<Tile,V>
	Method Compare( lhs:Tile, rhs:Tile )
		
		If lhs.x <> rhs.x
			Return lhs.x - rhs.x
		Else
			Return lhs.y - rhs.y	
		End
		
	End
End

However, you don't need to do this at all to use Maps. You've already got a suitable key to use: the grid index. You can just use the provided IntMap implementation as IntMap<Tile> and store tiles against their Grid array index, i.e. open.Set( t.x+t.y*width, t ). Obviously it would be more convenient to store the index on the tile to avoid the calculation every time.

That said, while you'll likely see a bit of a speed boost from using maps that way, your performance issues run deeper. Your code does a lot of repeated iterating through the open list to find the next best search node and maps aren't going to fix that.

FBEpyon

(Posted 2015) [#15]

Double post in error...

FBEpyon

(Posted 2015) [#16]

Okay well I will take at that when I get a chance, I loaded up my surface pro, and corrected the errors in the code, and its working now..


Import mojo

Class MyApp Extends App

	Field player:Tile
	Field target:Tile

	Field map:Grid

	Method OnCreate:Int()

		SetUpdateRate(60)
		player = New Tile(0,0)
		target = New Tile(8,8)

		map = New Grid(17,17)
		Print "Generating Map..."
		map.Generate(player,target)
		
	End

	Method OnUpdate:Int()
	
		If MouseX() < map.width*16 And MouseY() < map.height*16 And MouseX() >= 0 And MouseY() >= 0
	
			If MouseDown(MOUSE_LEFT)
			
				player.x = MouseX()/16
				player.y = MouseY()/16
				
				map.Generate(player,target)
			
			End
		
		End

	End

	Method OnRender:Int()

		Cls

		For Local n:Tile = Eachin map.data

			SetColor 255,255,255

			If map.path.Contains(n)

				SetColor 255,0,0

			EndIf

			DrawRect n.x * 16, n.y * 16, 16, 16

		Next
		
		SetColor 0,255,0
		
		DrawRect player.x * 16, player.y * 16, 16, 16
		
		SetColor 0,0,255
		
		DrawRect target.x * 16, target.y * 16, 16, 16

	End

End

'Tile class for storying the information about the current tile in the map (ex: x,y,style,etc.)

Class Tile

	Field x:Int, y:Int

	Field g:Int, h:Int

	Field parent:Tile

	Method New(_x:Int, _y:Int)

		x = _x
		y = _y
		g = 1000
		h = 1000

	End

	Method GetF:Int()

		Return g + h	

	End Method

End

'Grid is used to lay out the tiles and to assign a path based on the grids returning path list

Class Grid

	Field data:Tile[]

	Field width:Int, height:Int

	Field path:List<Tile>

	Method New(_width:Int, _height:Int)

		data = new Tile[_width * _height]

		width = _width
		height = _height

		path = New List<Tile>

		For Local x:Int = 0 Until width
		For Local y:Int = 0 Until height
		
			data[x + y * width] = New Tile(x,y)			

		Next
		Next

	End

	Method Generate:Void(s:Tile, t:Tile)
	
		path.Clear()

		Local start:Tile = data[s.x + s.y * width]
		Local target:Tile = data[t.x + t.y * width]

		Local open:List<Tile> = New List<Tile>
		Local clsd:List<Tile> = New List<Tile>

		Local current:Tile = start

		open.AddLast(start)
		
		While Not open.IsEmpty()
		
			For Local v:Tile = Eachin open
			
				If v.GetF() < current.GetF() Or v.GetF() = current.GetF() And v.h < current.h

					current = v

				EndIf

			Next

			open.Remove(current)
			clsd.AddLast(current)

			If current = target

				retrace(start,target)

				return

			End

			For Local n:Tile = Eachin neighbour(current)

				If clsd.Contains(n)

					Continue

				End

				Local newg:Int = current.g + distance(current,n)

				If newg < n.g Or Not open.Contains(n)

					n.g = newg
					n.h = distance(n, target)
					n.parent = current

					If Not open.Contains(n)

						open.AddLast(n)

					End

				EndIf

			Next
			
		End
		
		open.Clear()
		clsd.Clear()

	End Method
	
	Method retrace(s:Tile, e:Tile)

		Local current:Tile = e
	
		While current <> s
	
			path.AddLast(current)
			current = current.parent		
	
		Wend
	
		path.Backwards()	
	
	End
	
	Method distance(t1:Tile, t2:Tile)
	
		Local distx:Int = Abs(t1.x - t2.x)
		Local disty:Int = Abs(t1.y - t2.y)
		
		If distx > disty
		
			Return 14 * disty + 10 * ( distx - disty )
		
		End
		
		Return 14 * distx + 10 * ( disty - distx )
	
	End

	Method neighbour:List<Tile>(n:Tile)

		Local l:List<Tile> = New List<Tile>

		For Local x:Int = -1 To 1
		For Local y:Int = -1 To 1

			Local checkx:Int = n.x + x
			Local checky:Int = n.y + y

			If checkx >= 0 And checky >= 0 And checkx < width And checky < height

				l.AddLast(data[checkx + checky * width])

			End

		Next
		Next

		Return l

	End

End

Class TileMap<V> Extends Map<Tile, V>

	Method Compare(lhs:Tile, rhs:Tile)
	
		If lhs.x <> lhs.y
		
			Return lhs.x - rhs.x
			
		Else
		
			Return lhs.y - rhs.y
			
		End
	
	End

End

Function Main:Int()

	New MyApp
	Return 0

End

Its fast for what it is, I was just hoping that I would get some more performance out of it..

Samah

(Posted 2015) [#17]

I'm working on a DiddyMap class right now that supports IComparable and IComparator, plus adding some of the functionality in the other Diddy container classes.
Example mapping x,y coordinates to a String:

Import diddy.containers
Import diddy.diddymap

Function Main()
	' create the map
	Local dm:DiddyMap<Vector,String> = New DiddyMap<Vector,String>
	
	' set two keys and print the map
	dm.Set(New Vector(1,5), "hello")
	dm.Set(New Vector(2,1), "world")
	For Local k:Vector = Eachin dm.Keys()
		Print k.x + "," + k.y + "=" + dm.Get(k)
	Next
	
	' change a key and print the map
	dm.Set(New Vector(1,5), "goodbye")
	For Local k:Vector = Eachin dm.Keys()
		Print k.x + "," + k.y + "=" + dm.Get(k)
	Next
End

Class Vector Implements IComparable
	Field x:Int, y:Int
	
	Method New(x:Int, y:Int)
		Self.x = x
		Self.y = y
	End
	
	Method CompareTo:Int(other:Object)
		Local v:Vector = Vector(other)
		If x > v.x Then Return 1
		If x < v.x Then Return -1
		If y > v.y Then Return 1
		If y < v.y Then Return -1
		Return 0
	End
End

Output:

1,5=hello
2,1=world
1,5=goodbye
2,1=world

As you can see, you don't need to extend DiddyMap at all, you just implement one method in your key class.

FBEpyon

(Posted 2015) [#18]

Thanks, I will look at it more when I get home tonight.. I still have to combined my random terrain generation with my new path finding, and test to see if the dwarf will follow the path, and stop if the target is dirt, and start mining.. going to be a fun ride!

muddy_shoes

(Posted 2015) [#19]

It's certainly fast enough for small maps/minimal obstacles/limited queries but it definitely needs work if you're going to expand to bigger maps with more than a few pathfinding entities. If you want more help on the performance side just shout out.

By the way, your code breaks at some point when the map/path grows because you set the tiles g/h values to 1000 and trust the heuristics to push the start cell off the current reference. You're better off just setting them to zero and setting current to open.First at the top of the loop (or Null with an appropriate check in your best tile search).

FBEpyon

(Posted 2015) [#20]

By the way, your code breaks at some point when the map/path grows because you set the tiles g/h values to 1000 and trust the heuristics to push the start cell off the current reference. You're better off just setting them to zero and setting current to open.First at the top of the loop (or Null with an appropriate check in your best tile search).

I noticed this myself, and have already corrected that part, now I'm trying to get it to only detect the 4 direction neighbors so I don't have diagonal movement ...