Map-Drawing: Assigning a Coordinate System

[omorkved]

Create algorithm to take the room graph and assign a (reasonable) coord system to it (given the fact that the graphs created could have wildly different shapes, be disjoint, contain empty coordinates, etc.)

The expected result of this task is a module that will take info from game state and produce (possible temporary) structs that union together the room structs and a coordinate. i.e. sending in room info of a game should spit back a list of all the rooms each matched with a (unique & logical) coordinate.

This task will involve communication with game state (@adomiter )

[omorkved]

Question going into this task: Can I assume that game state/WDL will throw an error if given illogical room position/orders? I will make the assumption for now--can deal with illogical maps if time.

[mpcsh]

@omorkved You can always assume that by the time a map reaches you, it has been validated. For now, you can assume that the validation enforces that all doors are bidirectional, everything is 2D (i.e. no up/down), and that there are no portals or any other funny business.

[mpcsh]

Also, the first part of the task doesn't really seem necessary to me. Aren't rooms already represented as a graph (in the form of nodes with adjacency lists) in the game state?

[omorkved]

Also, the first part of the task doesn't really seem necessary to me. Aren't rooms already represented as a graph (in the form of nodes with adjacency lists) in the game state? @mpcsh

This is from #20 : "Given that a graph struct is overkill and most of the rooms will contain the information necessary, we just thought we would, in the game state, keep track of a list of all rooms. The order only matters insofar that the node is the room the player is currently in. We could eventually optimize so that the "most adjacent" are closer to the top. We are looking into setting up a hashtable with the id so that traversal is faster as we are given room ids."

I will talk to Game state about this! It's not a problem if they keep it in this format, just a bit more work.

[omorkved]

List of Questions for Game State: These are questions I created and will ask (have not asked yet!!) to Game State. (Or, @adomiter might ask these in her meeting with Game State)

1. Biggest question: I notice that there’s no directionality(North/south/east/west, possibly up/down) in the room struct in room.h (as of commit 59b9918) or in object.h (referring to commit 61e65dc). I see that rooms have a list of door objects and that each door contains a pointer to another room. Request: Could the door object or some other object also store directionality? Just like as a second field next to locked/unlocked. (Preferably as a tagged union!). This is the most important thing to UI—Map drawing is impossible without this! (I will double check with WDL that they are specifying direction, but I assume so since this was a pretty standard feature of our examples) EDIT: This is a priority for this Sprint! as per @mpcsh 's comment

2. Speaking of which... are we supporting up/down? (as in, second floor of a building). This might be a question for me to ask WDL too. It's just something I need to plan since it's a whole extra dimension. Of course this could be added later as another feature, but if we are for sure doing it I'd love to know from the start if possible! (Assuming 2D for now as per Mark's comment above)

3. Quote from somewhere in #20 "Moving to another room is by tracking the room id and using a hashtable." — Is there a spot where this hash table is explained in more depth and if so, could you point me there? I’m interested in calling on this hash table for a graph I might (possibly) create to track room locations

4. Not a question but a request: Issue #20 includes this comment: “Currently we removed the adjacency list design which saves the map of all the room, … This feature may be reconsidered in the future based on the actual design of WDL team.” Can you please let me know if this implemented! It doesn’t have to be, but having this list would definitely change how I implement the problem of map-drawing

[omorkved]

Point to consider for UI Team: Do we want rooms to only appear on the map as they are discovered? Or do we want to display the whole map from the start?

I will assume the latter for now, but this should be a relatively easy change to make later on. Later on, let’s say we decide to only print rooms the player has been in. We would talk to Game State about (hypothetically) storing this info in a discovered-room field (a simple yes/no) somewhere, if this is the case. When creating a coordinate system for printing, we can still store room info as normal coordinates. Then, our drawing function can simply skip over rooms that have the discovered-room switch turned off.

Conclusion: Whether or not we only display rooms once they are discovered should not impact assigning coordinates to rooms (since each room has a unique coordinate)

[borjasotomayor]

fyi, the sample graph code I referred to in the team meeting can be found here: https://mit.cs.uchicago.edu/cmsc15200-sum-18/graphs

Regarding the "overkill" comment in #20, this stems from something we told the Game State team on Slack:

Using an actual graph data structure would probably be overkill, even if linking the rooms/objects together can be thought of as a graph

Using lists or hash tables to link rooms together would be enough

(note that we provide a list and hash table implementation inside the src/include/ directory)

fyi, linking the rooms together with lists will likely result in what's called an "adjacency list" (https://en.m.wikipedia.org/wiki/Adjacency_list)

So, the point is that the way they're storing the rooms is effectively already graph-like, and that there isn't really a need to use a generic graph data structure (like the one you'll find in the link above).

[mpcsh]

@omorkved Borja beat me to the punch there, but that's the point.

I think the issue regarding directionality should be communicated more as a hard requirement than a request. Very few things can function without it (e.g. when someone types GO NORTH, game state won't know what room to move to). That's not to say don't be polite about it, but rather I would take out things like "at your discretion", and adjust the language to get the point across that this is an absolutely mission critical requirement.

[adomiter]

Formal Interaction with Game State Number 1: This is just a quick summary of the points that we were able to discuss in person. If we have any more questions, we can reach Patrick or any of the other Game State members via Slack.

Anticipated changes to the room struct:

• possibly expansion to support list of exits and features that involve storing and manipulating the inventory list

Directionality:

• 6 directions: North, South, West, East, up, and down
• Use of a hash table: directionality will be converted into numeric values rather than being stored as chars
• the game-state team is thinking to include portals as an additional feature in later sprints

Levels:

• As of right now, only up and down will be supported. The notion of having different levels exceeding two is something that we should not worry about during this sprint.

Game struct and the list of rooms:

• the game struct will have a list of the rooms that will allow us to iterate through each room and find the rooms connected to it
• this will most likely be the best struct to work with when doing BFS

Questions that we need to think about:

• How do we want to keep track of coordinates?
• Do we want a coordinate struct that is null in the beginning and we fill in when the game is initialized? Would this feature be included in the struct denoted by game-state?
• Is there another way that we can keep track of this information within the UI only?

*A possible solution that I would like all of your feedback on**

• Would we like game-state to create a function that will assist us in iterating through the history of a player? In other words, we would be able to call on a function that will output a list of rooms that a user has been in and using that information, we would only display those rooms. If so, they can add this to their back log.

Remaining Thoughts/Concerns:

• Because the notion of using coordinates is very unique to UI, we should probably use the general code written by game state. Having these specific add-ons might complicate the work that other groups are doing (more specifically WDL).

[omorkved]

For Game State

• the game-state team is thinking to include portals as an additional feature in later sprints

If portals are added, please list them as a seventh direction (after N/E/S/W/Up/Down)! So that our search function knows that rooms in this "special direction" are not adjacencies

• As of right now, only up and down will be supported. The notion of having different levels exceeding two is something that we should not worry about during this sprint.

That's fine!

Game struct and the list of rooms:

• the game struct will have a list of the rooms that will allow us to iterate through each room and find the rooms connected to it
• this will most likely be the best struct to work with when doing BFS

A little confused by this description of a game struct! I was just going to go into the initial room and iterate through all of the rooms with BFS from there. So the current struct with a list of door objects is fine.

Questions that we need to think about:

• How do we want to keep track of coordinates?
• Do we want a coordinate struct that is null in the beginning and we fill in when the game is initialized? Would this feature be included in the struct denoted by game-state?

Yes! Would love that. Within the room struct, Could you please add a pointer to a coord struct, initalized as null. (where coord is a simple struct to int fields x y and z). We can fill it in with the algorithm we are making for this issue. Let's talk more about this between the two teams

@patrickkoopmans Edit Honestly we might not even need a coord struct in game state-- we could just make our own coord struct and store coord to room info in a hash table (since it looks like UI might be the only ones using coordinates). So you guys can hold off on this

(Also, removed request for mark done field. Not needed in game struct)

If anyone from WDL reads this, a clarification--we don't need WDL to support coordinates; we are inferring them from the north/east/south/west info.

A possible solution that I would like all of your feedback on*

• Would we like game-state to create a function that will assist us in iterating through the history of a player? In other words, we would be able to call on a function that will output a list of rooms that a user has been in and using that information, we would only display those rooms. If so, they can add this to their back log.

Probably not necessary as a function! If action management (?) or us chooses to support noting when a player has discovered a new room, there can just be a Discovered bool in the room struct

@adomiter Is posting a more thorough summary of this in slack and below @patrickkoopmans Let me know if questions on this!

[adomiter]

---

This is the message that we will be posting to the general chat in Slack; I am adding it as a comment here for reference later on.

Hi Game-State team! After reviewing the notes that I took after our initial meeting, we have a few more requests that we would like to make. Again, it is totally up to you all as a team to decide to follow through with them but these are very crucial to our mapping function. It would be great to have these concerns addressed as soon as possible.

Assumptions that we are making: we are assuming that there are only 6 directions, all rooms are the same size, and there is only one ‘real’ exit for each wall - All rooms being the same size is crucial for map drawing

1. If we choose to support portals in the future, we need to be added as a seventh direction so that our mapping function does not draw these rooms next to each other.

2. If there will be more than one exit attached to one wall, it will have to be entering the same room (We prefer that this feature is not implemented (yet) because it will make BFS harder to do)

3. If you want fake doors, then it needs to denoted with a unique name or struct. And by fake doors, I mean doors that do not lead to another room and are locked.

4. List of exits: this list currently has the door objects, we would like for you all to assign a direction to each door 


Add three more fields:

• Specific to UI function: ‘marked done’ field within the room struct that is a boolean

• One pointer to a coordinate struct within the room struct that is null at the beginning of the game and our algorithm will fill in the coordinate struct as the game goes: we are currently taking an algorithm that takes in the list of exits

• ’Discovered’ field that is denoted as a boolean: this tells us if the player has already entered the room It should be noted that this field is not a huge priority and is dependent on whether as a class, we wanted the map to only display the rooms that a player has been in.

It would be great if we had a somewhat-finished struct that we can refer to during this sprint. Thank you.

If confused on this, please contact Olivia asap!

---

[omorkved]

Backtracking Algorithms research (done with @adomiter ): Conducted due to conversation with @mpcsh about the need to use backtracking. As we traverse through the rooms using BFS or DFS, we may initially assume false distances between rooms that result in drawing two rooms in one coordinate even though the game design is logical. We need a way to backtrack whenever we are about to assign duplicate coordinates and instead adjust distances between points. The underlying assumption here that Mark and I were making is that passages can have lengths (i.e. we might have a room in logical spot (0,0) connect to a room in logical spot (2,0)). ie a game writer could have an initial room r1 where you go south, go east, go north, go west, but reach a different room (r5), because the distance walked east was twice the distance walked west. This becomes more apparent when diagrammed visually

N-Queens problem -- second half of this page: https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/ Helpful algorithm here. Notably, in this problem we are given the dimensions beforehand. We are not given the dimensions beforehand in our Room problem

The Rat-Maze problem seems similar to our Rooms problem: https://www.tutorialspoint.com/Rat-in-a-Maze-Problem This was also really helpful to read through although in C++ --> In this problem, you can only move in two directions (right/down). My worry with the four directions in our Room Problem is that, if the rooms are all in one giant loop, when we backtrack and unmark certain rooms as discovered, we don't want to accidentally unmark all of the rooms and be stuck in an infitine loops. Have to be careful about this. -->They use a 2D array, which we cannot use because we have no limit (yet) as to how many rooms we can have and how far out they can go. -->They have a simple end goal (has the end room been reached?) Contrast with our end goal--has every room been assigned a coord. I suppose we have assigned every room a coordinate once our stack/queue of unmarked rooms to-explore is empty.

Update 5/8/19 After discussion with Prof. Borja in office hours, we will not be supporting connections with "distances" in this sprint. This takes out the need for a backtracking algorithm (for now).

[mpcsh]

One issue with the request to game state: they should not be including the "marked done" field. This should live inside some kind of map node struct and be solely this team's responsibility.

[omorkved]

Update: I fixed the find_coord functions and now the hash table successfully stores and retrieves rooms using coordinates as keys! We will close this issue tomorrow to do a bit of testing on our DFS now that the hash works (See commit 59f3ce569bb and c02f0a265)

@adomiter

[adomiter]

Notes:

• The find_room function needs to be finalized with game-state room/game structs.
• We expect that WDL will call on our "begin-breadth-first-search" function (maybe we should change the name to check_valid_map) so that it is more general.
• We expect to be calling on game-state structs that contain data at the start of the game to display the map.

@omorkved

[omorkved]

• We expect that WDL will call on our "begin-breadth-first-search" function (maybe we should change the name to check_valid_map) so that it is more general.

Ooh yeah I like that name change idea, that will make it more clear to WDL what the purpose of our function is. let's do it @adomiter

[adomiter]

Ready to close this issue. Please refer to final commit 057da12

@mpcsh @borjasotomayor

Testing the check_valid_map will be another task for sprint 3 so that we will be able to integrate game-state's final structs.

Closing Statement: The coordinate related functions have been implemented and works with UTHash. The find_room function needs to be finalized with game-state room/game structs in Sprint 3 and we have decided that unit tests will be a task for Sprint 3 as well. We will also be creating a backlog task related to further developing how we assign coordinates (e.g. backtracking).

[mpcsh]

Issue Score: ✓+

Comments: Fantastic work here!