User Tools

Site Tools


spcs:summer2014:day_9

SPCS - Day 9

Row 1: Boys! (+ Christine and Joyce)

Afternoon Groups: (Olivia, Caelen, Nidhi), (Rohan, Jon), (Joyce, Neel,Tony), (Jonathan, Christine, Rahul), (Jerry, Sindhu, Akane), (Maxine, Vrinda, Jannani)

Topics

  • Alarmed doors
  • Different types of Graphs
  • Revisit Data Structures
  • A*
  • 10:00 Lydia Choy
  • Game Theory
  • Prisoners Dilemma
  • Psychology
  • Revisit OOP

Graph Search code in Java:

import java.util.*;
 
public class GraphSearch {
 
	public static void main(String[] args){
		int[][] graph = {{1,1,0,1,0},{0,0,0,0,1},{1,1,1,0,0},{1,1,1,1,0},{0,0,0,0,0}};
 
		/*
		for (int i=0;i<3;i++)
			for (int j=0;j<3;j++)
				System.out.println(graph[i][j]);
		*/
 
		//depth(graph,3);
 
		breadth(graph,0);
	}
 
	public static void depth(int[][] graph, int root){
 
		// x is where it's going
		// y is how you get there
 
		for (int i=0;i<graph.length;i++)
			graph[i][root] = 0;				
                        // set the return values to 0
 
		System.out.println(root);
 
		for (int i=0;i<graph.length;i++){
				if (graph[root][i]==1)
					depth(graph,i);		
			}	
	}
 
	// =======================================================
 
 
	public static void breadth(int[][] graph, int root)
	{
		Queue<Integer> q = new LinkedList<Integer>();
 
		for (int i=0;i<graph.length;i++)
			graph[i][root] = 0;				
                        // set the return values to 0
 
		q.add(root);
		System.out.println(root);
 
 
		while(!q.isEmpty()){
			root = q.remove();
			for (int i=0;i<graph.length;i++) {
				if (graph[root][i]==1){
					System.out.println(i);
 
					for (int j=0;j<graph.length;j++)
						graph[j][i] = 0;				
                                                // set the return values to 0
					q.add(i);
				}
			}		
		}	
	}
}

Assignments

Part 0: Blog - Please make sure you've blogged all you past projects when you are done

Make sure to github and blog all projects. This is required!

Part 1: Blog - Final Project Proposal (Individual)

Mousey the mouse heard that the Exploratorium was pretty cool. He's wondering if our class could pull together an exhibit of similar displays. Mousey was too small to use the mechanical devices, so he'd prefer computer programs or just smaller demos.

Please pick one topic of your interest, could be about anything we talked about in class, anything you saw at the Exploratorium, this list here: Final Projects, or something creative you think of. Now you will write a project proposal.

In your post you must answer the following:

  1. What is your prototype about?
  2. What will people learn from your experience?
  3. Will it be interactive or is it something people will watch? If interactive, what can the user do?
  4. How would your design fit in with the Exploratorium? Describe your experience from yesterday and include pictures. Use examples!
  5. Draw a diagram that explains how your prototype works.
  6. Are there any existing systems that are similar to yours? Name and link them.

Part 2: Bouncing Balls: Objects and Collision (Teams)

Review: Go back to the lecture on Bouncing Balls. Try to create your own Ball class that can bounce around the screen.

Make 4 balls bounce around the screen.

  • ball 1 goes left and right
  • ball 2 goes up and down
  • ball 3 goes diagonal
  • ball 4 goes diagonal and moves when the player clicks the screen

You must create a Ball class.

Part 3: Mousey's Travels (Teams)

Please try to find one path that visits everyone. You do not need to find the shortest one, but try to find the shortest path after you've successfully drawn a path to everyone's home.

For an additional challenge, try to find a round trip path back home that is the shortest. Starting at Stanford and ending at Stanford. You can find a way to make this program interactive or animated.

Part 4: A* Search (Teams)

We've talked about Depth-First and Breadth-First Search. Now, let's do A* Search. A* is used for AI Pathfinding.

Try this part ONLY if you feel up to the coding challenge.

Here are some resources on A*

Please read this article on A*: http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

This is the demo I showed in class: http://classes.soe.ucsc.edu/cmps179/Spring13/Final/edaramir/index.htm

For examples: http://www.openprocessing.org/search/?q=pathfinding

If you can make it this far, then try creating Mousey a maze.

Mousey is on a 32 x 32 grid. Put a piece of cheese on the board, either hard coding or using the user's mouse click input. Use ANY search algorithm to find the cheese. Put up walls for your maze and see how it works.

Part 5: Cookbook FPS (Teams)

Work on the First Person Shooter from the Cookbook. This is an intro to 3-D.

Feedback!

/soe/sherol/.html/teaching/data/pages/spcs/summer2014/day_9.txt · Last modified: 2014/07/03 12:19 by ffpaladin