Real-time Community Navigation System — GSAPP 2018Fall Datamining the City through Processing
Authors ：Nengjing Deng (nd2559), Danting Luo (dl3149), Shulin Zhang (sz2586)
Research Question: What will be the best response to a travel demand in a neighborhood?
One Sentence ：A real-time navigation system with weighted factors providing best routes for randomly distributed starting points and destinations in a simulated community.
Glossary:
individuals (agents) — cars
Environment — simulated city environment with different functional areas ( e.g the residential area, commercial area, industrial area, and recreational areas such as green space and theme park), which have different urban density and thus have different impacts on their surrounding streets
Behavior — cars will choose the optimized route with the least time from the starting point to the destination point
Parameters — cars will have different speeds on different streets
Input — parameters include randomly selected starting points, randomly selected destination points, and randomly designated paths with different traffic congestion levels affected by city’s functional areas.
output — the optimized route with the least time from the starting point to the destination point
Intro:
With the acceleration of urban modernization construction, the transportation system is changing rapidly every day. Along with urban roads and municipal engineering construction continuously updated, and the complexity of urban streets also becomes more aggravated. As the most important means of transportation in the city, the mode of walking must deal with the changing urban traffic and will depend on different conditions of individuals. Individuals merely relying on one’s memory is unable to cope with such a rapid-changing traffic development. Therefore, people need a toolkit that can accurately provide them with the best personal-tailed routing.
GPS (Global Positioning System) navigation technology was subsequently created. The basic principle is to use the instantaneous position of the satellite in rapid motion as the known starting data and use the method of spatial distance resection to determine the location of the point to be measured. With the help of geographic information data, users will have more accurate road guidance.
Compared to other competitors, Google entered the navigation system field relatively late. Its system was only a few months old when it was shown to Tim O’Reilly in 2005. Google Maps provides navigation directions and plan the best route from one’s starting location to his destination, based on Google’s encrypted algorithm and living traffic prediction based on previous traffic data.
The world expertise of worldwide navigation system like Google Map makes people’s life easy, efficient and convenient. Through simulating such navigation system at the community level and thinking about local activities such as small street events and community festivals, we hope to learn and develop a local specialized navigation system for community residents like Google map.
Model
Our model is based on the Dijkstra algorithm that was proposed by the Dutch computer scientist Azhel Dextra in 1956. This algorithm is often used in routing algorithms or as a sub-module of different graph algorithms. For example, if the nodes in the graph represent cities and the weights on the edges represent the distance and traffic flow traveled between cities, the algorithm can be used to find the shortest path between two cities.
Dijkstra Algorithm：
- Firstly, we can specify a node, for example, we want to calculate the shortest path from ‘A’ to other nodes
- Secondly, we introduce two sets (S, U), the S set contains the points of the shortest path that have been found (and the corresponding shortest length), and the U set contains the points where the shortest path is not found (and the path from A to the point, as shown in the above figure, A->C is not directly connected, therefore, the initial length is ∞)
- Thirdly, we initialize two sets: the S set initially has only A->A = 0,the U set initially has A->B = 4, A->C = ∞, A->D = 2, A->E = ∞
- Fourthly, we find the shortest point from the U set and add it into the S set, if ( ‘D to B, C, E distance ‘ + ‘AD distance ‘ < ‘A to B, C, E distance ‘). For example, we found A->D = 2 is the shortest distance between A and D, we then update it into the U set,
- We update the U set by repeating the fourth step until the end of the traversal and get the shortest path from A to all other nodes in the graph
Our Narrative:
We take cars as the agents in our simulated environment, which is regarded as a city with different functional areas (e.g the residential area, commercial area, industrial area and recreational areas such as green space and theme park), therefore, we assume that different functional areas with different urban density along the street will have different impacts on it ( like Google Map, the color of the streets represents different levels of traffic congestion, with red representing the most congested road, green representing the lease congested road, and yellow representing the median congested road, which will be changed everytime we run the model). Hence, cars on different streets will have different travel speeds: on the red roads, the cars will have the slowest speed; on the green roads, the cars will have the highest speed, and on the yellow roads, the cars will have the median speed.
Two ways of applying the Dijkstra algorithm:
The Dijkstra algorithm can be used in various ways: the original version of the Dijkstra algorithm is applied to find the shortest path from one node to another, which is a typical algorithm used to calculate the shortest path between two nodes. While another version of the Dijkstra algorithm is that one takes up a node as the source node and then finds the shortest routes to the other nodes in the graph, which produces the shortest path tree.
Both versions are realized in our models: in our first experiment (the gif is shown above), everytime we run the model, the starting point of a car will be randomly chosen. As we move the mouse on our “simulated city environment”, the destination point will be automatically designated, and in the meantime, the corresponding shortest path and its distance (unit: mile) will also be shown in the map as well. While in our second experiment ( the gif is shown below), everytime we run the model, the only destination point is chosen automatically, together with five randomly selected starting points. Five cars will be moving from their starting points to the only destination point in the sametime, with different speeds, on their own optimized paths. However, due to different paths and speeds, they will not arrive destination point together.
Learnings
While developing the model, we learned from using the Dijkstra algorithm, and the comparison of the Dijkstra algorithm with other best-routing problem-solving algorithms. Meanwhile, to understand the factors that can impact on routing and time cost, we referred to previous literature work for deciding the weights and significance of different elements for more accurate inputs and a more simulated environment.
Deciding which algorithm to be used in our study is one of the most critical steps in our model building process. There are several possible algorithms other than Dijkstra algorithm that can be used for best routing question, including the Bellman-Ford Algorithm, Shortest Path Faster Algorithm (SPFA), and Floyd Algorithm. Dijkstra algorithm is most applicable to a dense map with adjacent matrix because a dense graph problem is closely related to the vertex. The Ford Algorithm is applied mostly in sparse maps because in this case routing is determined more by edges. Floyd Algorithm combines both and can be used to most plans. The SPFA algorithm can solve the problem of negatively weighted factors and is less complicated than Ford. In some cases, it is viewed as another combination of the Dijkstra Algorithm and the Ford Algorithm. All these algorithms can handle routing problems in most maps, either with directions or without directions. We found that different major part of these four algorithms is centered on whether these algorithms determine the route by initializing by adjacency matrix’ vertex or adjacency tables’ edges. The reason for choosing Dijkstra algorithm is because that, even though the Floyd Algorithm and the Ford Algorithm with negatively-weighted factors and edges, however, they both require the final weight loop’s sum cannot be smaller than zero. Considering the reality and the traffic environment of most major downtown areas, as well as the current shortcomings of these available algorithms we choose to undertake the Dijkstra Algorithm to perform our best routing question.
With the best routing algorithm decided, the next step we want to look at users of different groups and how factors can result in the transit environment. Though at this stage we have not yet include human-beings in our system, we still want to understand how people of different physical conditions and background may vary regarding walking as a prevalent mode of for the general public. Residents of community navigation can differ significantly. Different groups of people have different habits for different ways of transit. Residential self-selection of transportation modes is an increasingly important issue. In addition to personal preference, transit decision depends on factors beyond built environment and access to transit service. (Li 2018) The multivariate models proposed by Ettema and Nieuwenhuis (2017) show that both travel attitude and travel being a reason for location choice influence travel mode use. Hence, preferences for and attitudes toward travel modes may systematically differ between different geographical settings. In addition to that, recent studies developed walkability models combining various built environment characteristics to predict walking optimally. Factors including age, sex, self-reported health status will result in different walking habits. (Lovasi et al. 2008) Kang and Dingwell (2008) concluded that the greater variability observed in the gait of older adults might result more from the loss of strength and flexibility than from their slower speeds. Our model will have various inputs because we have a large group of the population ranging from 10 to 70, from young female professionals to disabled seniors, with differing walking speed. Such will provide a more accurate routing with time cost information for every user.
Moreover, other environmental factors also have an impact on determining routing decision by impacting on the traffic flow and time cost. In an agent-based model of the daily commute study developed by Ge and Polhill (2016), four factors are confirmed that they significantly contribute to the daily commute time: flexitime range (f), urban concentration (u), bypass(b), and road attribute(c). Flexitime is a time range within which individual can choose when to arrive at the location. Urban concentration describes the density of population living in the downtown area. Bypass represents the road network, and road attribute explains the road types and its carry capability to expect how busy it will be. Ge and Polhill’s study found that flexitime and urban concentration impact on commuting time cost positively, while bypass has a negative impact. In our model, we integrate urban concentration by estimate population density concerning different zoning regulations of the blocks surrounding the roads. The population density will have an impact on the street carrying capacity. Together with road attributes (including traffic lane amounts), we can estimate the traffic flow volume and thus the flow speed. The reason for not including flexitime and bypass is because that our premise of the model is that every user wants to find the best routing with the least time needed, and in a community with grid network like we have simulated, the total bypass from a certain starting point to the destination is the same in any shortest routes. Therefore, the distance is not the only factor in determining the time cost, but the road condition, influenced by traffic flow and road attributes, also shapes the moving speed.
In our models, these variables have been carefully studied and considered. Though not fully weighted and integrated into the algorithm, our current model shows a draft version of the final product, with community information missing. With all the information in hand and a thoughtfully, comprehensively and all-inclusive developed model, the final routing recommendation will be the most user-tailed navigation guidance for the community residents.
Future Implications
As time goes by, we’re increasingly moving towards a simulation economy, where any kinds of analysis give way to real-world data, hypotheses and learning process. Our model not only can improve people’s daily life by keeping them away from traffic congestion and providing them with the optimized decided routes but also can be further applied in the new technique called simulation-based planning that is useful for route planning under certain circumstances and locations. Because simulation is the only tool that we can use to make the most effective decision in uncertain and complicated environments, which provides the system with useful information for hypothesis and formulates sequences of actions that would happen in the future if a plan is implemented (Fishwick,1995)
Since the simulation analysis can be used to track real execution performance, reflect actual processes, predict more accurate and comprehensive outcomes (Jin and Paul, 1995), It will definitely change the way we live in the urban area as we will be able to make the most effective decision and the most optimized strategies and thus save time for living our lives. It will also emphasize the characteristics of each or each simulation system user, as in our imagination, each can personalize their simulation system so that the information and generated and provided to them will be the most appropriated and optimized for them.
We learn from Google simulation and want to use this model to create a real-time navigation system with weighted factors providing best routes from a randomly selected starting point to a randomly selected destination point. While other than that, in the meantime, we hope to personalize our agents of different characteristics and show them with personalized simulation information like the optimized routes. By now, we have simulated a community with grid patterns of network roads and randomly distributed traffic flow on each segment of paths, based on the application of the Dijkstra Algorithm. As parameters including randomly selected starting points and destinations, urban concentration density and road attribute like lane width and number change, our outputs of the optimized routes will change simultaneously as well.
In the future, we expect that we could first promote this system to every community with community-specific features and residents information. With recorded and calculated community traffic condition and documented residents’ preference for all transit modes, our system will be the best tool to every user. Also, we expect that other parameters can change to make our routing more personal-tailed based on users’ different characteristics. Looking forward, with enough funding and expertise, system users can even personalize which kinds of roads, neighborhoods, and city landscape they prefer, with more detail information like weather and city structure under construction automatically generated for them as well. Other algorithms may also be integrated depending on the community’s nature. The system we have now would ultimately be sufficiently developed to a business product that can be used in most neighborhoods and provide the best user experience because it has the most up-to-date community traffic information and caters every user by their individual preferences.
Code (code is commanded and worked together by group members)
Code of First Experiment
def setup():
size(1850,1850)
frameRate(100)
#def draw():
global blocksize, roadwidth, n, m,numend,x3,y3
blocksize=150
roadwidth=50
n=9
m=n+1
numend=5
#generating two points randomly
global direct1,xloc1,yloc1,a1,b1,r,g,b
direct1=int(random(2)) #0=north<->south, 1=east<->west
xloc1=int(random(1,m))
yloc1=int(random(1,m))
a1=int(random(m-1))
b1=int(random(m-1))
global x1,y1
if direct1==0:
x1=xloc1*(blocksize+roadwidth)+roadwidth/2
y1=a1*(blocksize+roadwidth)+int(random(blocksize))+roadwidth
else:
x1=b1*(blocksize+roadwidth)+int(random(blocksize))+roadwidth
y1=yloc1*(blocksize+roadwidth)+roadwidth/2global direct2,xloc2,yloc2,a2,b2,ii
global x2,y2
x2=[0 for i in range(numend)]
y2=[0 for i in range(numend)]
for i in range(numend):
direct2=int(random(2)) #0=north<->south, 1=east<->west
xloc2=int(random(1,m))
yloc2=int(random(1,m))
a2=int(random(m-1))
b2=int(random(m-1))
while (xloc1==xloc2 and a1==a2) or (yloc1==yloc2 and b1==b2):
direct2=int(random(2)) #0=north<->south, 1=east<->west
xloc2=int(random(1,m))
yloc2=int(random(1,m))
a2=int(random(m-1))
b2=int(random(m-1))if direct2==0:
x2[i]=xloc2*(blocksize+roadwidth)+roadwidth/2
y2[i]=a2*(blocksize+roadwidth)+int(random(blocksize))+roadwidth
else:
x2[i]=b2*(blocksize+roadwidth)+int(random(blocksize))+roadwidth
y2[i]=yloc2*(blocksize+roadwidth)+roadwidth/2
global index, optimal, last, weight
index = [0 for i in range(m**2+1+numend)] #determine if the best path from point i to starting point is found. 0=no, 1=yes
optimal = [9999.99 for i in range(m**2+1+numend)] #length of the best path
last = [0 for i in range(m**2+1+numend)] #last crossing in the best path
weight = [[9999.99 for x in range(m**2+1+numend)] for y in range(m**2+1+numend)]
#determine weight for each road section
for i in range(n):
for j in range(m):
weight[i*m+j+1][(i+1)*m+j+1]=(random(1,10))
weight[(i+1)*m+j+1][i*m+j+1]=weight[i*m+j+1][(i+1)*m+j+1]
weight[j*m+i+1][j*m+i+2]=(random(1,10))
weight[j*m+i+2][j*m+i+1]=weight[j*m+i+1][j*m+i+2]
global X, Y
X=[[0 for i in range(m)] for j in range(m)]
Y=[[0 for i in range(m)] for j in range(m)]
for i in range(m):
for j in range(m):
X[i][j]=j*(blocksize+roadwidth)+roadwidth/2
Y[i][j]=i*(blocksize+roadwidth)+roadwidth/2
if X[i][j]==x1 and (y1-Y[i][j])>0 and (y1-Y[i][j])<(blocksize+roadwidth/2):
weight[0][i*m+j+1]=weight[i*m+j+1][(i+1)*m+j+1]/(blocksize+roadwidth)*(y1-Y[i][j])
weight[0][(i+1)*m+j+1]=weight[i*m+j+1][(i+1)*m+j+1]-weight[0][i*m+j+1]
weight[i*m+j+1][0]=weight[0][i*m+j+1]
weight[(i+1)*m+j+1][0]=weight[0][(i+1)*m+j+1]
for ii in range(numend):
if X[i][j]==x2[ii] and (y2[ii]-Y[i][j])>0 and (y2[ii]-Y[i][j])<(blocksize+roadwidth/2):
weight[m*m+1+ii][i*m+j+1]=weight[i*m+j+1][(i+1)*m+j+1]/(blocksize+roadwidth)*(y2[ii]-Y[i][j])
weight[m*m+1+ii][(i+1)*m+j+1]=weight[i*m+j+1][(i+1)*m+j+1]-weight[m*m+1+ii][i*m+j+1]
weight[i*m+j+1][m*m+1+ii]=weight[m*m+1+ii][i*m+j+1]
weight[(i+1)*m+j+1][m*m+1+ii]=weight[m*m+1+ii][(i+1)*m+j+1]
if Y[i][j]==y1 and (x1-X[i][j])>0 and (x1-X[i][j])<=(blocksize+roadwidth/2):
weight[0][i*m+j+1]=weight[i*m+j+1][i*m+j+2]/(blocksize+roadwidth)*(x1-X[i][j])
weight[0][i*m+j+2]=weight[i*m+j+1][i*m+j+2]-weight[0][i*m+j+1]
weight[i*m+j+1][0]=weight[0][i*m+j+1]
weight[i*m+j+2][0]=weight[0][i*m+j+2]
for ii in range(numend):
if Y[i][j]==y2[ii] and (x2[ii]-X[i][j])>0 and (x2[ii]-X[i][j])<(blocksize+roadwidth/2):
weight[m*m+1+ii][i*m+j+1]=weight[i*m+j+1][i*m+j+2]/(blocksize+roadwidth)*(x2[ii]-X[i][j])
weight[m*m+1+ii][i*m+j+2]=weight[i*m+j+1][i*m+j+2]-weight[m*m+1+ii][i*m+j+1]
weight[i*m+j+1][m*m+1+ii]=weight[m*m+1+ii][i*m+j+1]
weight[i*m+j+2][m*m+1+ii]=weight[m*m+1+ii][i*m+j+2]
weight[0][0]=0
for ii in range(numend):
weight[m*m+1+ii][m*m+1+ii]=0
# Dijkstra Algorithm
global minimum, mini
index[0]=1
optimal[0]=0 #i=0 represents starting point
for k in range(m**2+1+numend):
for i in range(m**2+1+numend):
if index[i]==1:
for j in range(m**2+1+numend):
if index[j]==0:
if optimal[i]+weight[i][j]<optimal[j]:
optimal[j]=optimal[i]+weight[i][j]
last[j]=i
minimum=9999.99
mini=0
for i in range(m**2+1+numend):
if index[i]==0 and optimal[i]<minimum:
minimum=optimal[i]
mini=i
index[mini]=1
#verify
print weight
print index
print X
print Y
print optimal
print last
def draw():
clear()
background(0)
#building the neighborhood
for i in range(roadwidth,width,blocksize+roadwidth):
for j in range(roadwidth,width,blocksize+roadwidth):
fill(50)
stroke(0)
strokeWeight(3)
rect(i,j,blocksize,blocksize)
for i in range(n):
for j in range(m):
if weight[i*m+j+1][(i+1)*m+j+1]<5:
r= (weight[i*m+j+1][(i+1)*m+j+1]-1)/4*255
g=255
b=0
else:
r=255
g=255-( weight[i*m+j+1][(i+1)*m+j+1]-5)/5*255
b=0
fill(r,g,b,150)
noStroke()
rect(X[i][j]-15,Y[i][j]+25,30,150)
#fill(0)
#myfont=createFont("Arial",30)
#textFont(myfont)
#text( weight[i*m+j+1][(i+1)*m+j+1],X[i][j]-20,Y[i][j]+100)
if weight[j*m+i+1][j*m+i+2]<5:
r=( weight[j*m+i+1][j*m+i+2])/4*255
g=255
b=0
else:
r=255
g=255-( weight[j*m+i+1][j*m+i+2]-5)/5*255
b=0
fill(r,g,b,150)
noStroke()
rect(X[j][i]+25,Y[j][i]-15,150,30)
#fill(0)
#myfont=createFont("Arial",30)
#textFont(myfont)
#text(weight[j*m+i+1][j*m+i+2],X[j][i]+100,Y[j][i])
#draw the optimal path
global p, q,minimum2
'''for ii in range(numend):
p=m*m+1+ii
q=last[p]
stroke(255,255,255)
strokeWeight(3)
line(x2[ii]-10+ii*20/numend,y2[ii]-10+ii*20/numend,X[int((q-1)/m)][int((q-1)%m)]-10+ii*20/numend,Y[int((q-1)/m)][int((q-1)%m)]-10+ii*20/numend)
p=q
q=last[p]
while q<>0:
line(X[int((p-1)/m)][int((p-1)%m)]-10+ii*20/numend,Y[int((p-1)/m)][int((p-1)%m)]-10+ii*20/numend,X[int((q-1)/m)][int((q-1)%m)]-10+ii*20/numend,Y[int((q-1)/m)][int((q-1)%m)]-10+ii*20/numend)
p=q
q=last[p]
line(X[int((p-1)/m)][int((p-1)%m)]-10+ii*20/numend,Y[int((p-1)/m)][int((p-1)%m)]-10+ii*20/numend,x1-10+ii*20/numend,y1-10+ii*20/numend)
fill(0,0,255)
strokeWeight(0)
ellipse(x1,y1,30,30)
fill(255,0,0)
strokeWeight(0)
ellipse(x2[ii]-10+ii*20/numend,y2[ii]-10+ii*20/numend,20,20)'''
x3=0.00
y3=0.00
x3=mouseX
y3=mouseY
minimum2=9999.99
i=int(x3/200)
if i==n:
i=n-1
j=int(y3/200)
if j==n:
j=n-1
if sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]<minimum2:
minimum2=sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]
mini=j*m+i+1
j=j+1
if sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]<minimum2:
minimum2=sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]
mini=j*m+i+1
i=i+1
if sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]<minimum2:
minimum2=sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]
mini=j*m+i+1
j=j-1
if sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]<minimum2:
minimum2=sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]
mini=j*m+i+1
stroke(255,255,255)
strokeWeight(5)
q=mini
line(x3,y3,X[int((q-1)/m)][int((q-1)%m)],Y[int((q-1)/m)][int((q-1)%m)])
p=q
q=last[p]
while q<>0:
line(X[int((p-1)/m)][int((p-1)%m)],Y[int((p-1)/m)][int((p-1)%m)],X[int((q-1)/m)][int((q-1)%m)],Y[int((q-1)/m)][int((q-1)%m)])
p=q
q=last[p]
line(X[int((p-1)/m)][int((p-1)%m)],Y[int((p-1)/m)][int((p-1)%m)],x1,y1)
fill(0,0,255)
strokeWeight(0)
ellipse(x1,y1,30,30)
fill(255,255,0)
strokeWeight(0)
ellipse(x3,y3,20,20)
myfont=createFont("Arial",40)
textFont(myfont)
text(minimum2*5,x3,y3)
Code of Second Experiment:
def setup():
size(1850,1850)
frameRate(100)
#def draw():
global blocksize, roadwidth, n, m,numend,x3,y3,spdctrl
blocksize=150
roadwidth=50
n=9
m=n+1
numend=5
spdctrl=0.03
#generating two points randomly
global direct1,xloc1,yloc1,a1,b1,r,g,b
direct1=int(random(2)) #0=north<->south, 1=east<->west
xloc1=int(random(1,m))
yloc1=int(random(1,m))
a1=int(random(m-1))
b1=int(random(m-1))
global x1,y1
if direct1==0:
x1=xloc1*(blocksize+roadwidth)+roadwidth/2
y1=a1*(blocksize+roadwidth)+int(random(blocksize))+roadwidth
else:
x1=b1*(blocksize+roadwidth)+int(random(blocksize))+roadwidth
y1=yloc1*(blocksize+roadwidth)+roadwidth/2global direct2,xloc2,yloc2,a2,b2,ii
global x2,y2,runx,runy,spd
x2=[0 for i in range(numend)]
y2=[0 for i in range(numend)]
runx=[0 for i in range(numend)]
runy=[0 for i in range(numend)]
spd=[0 for i in range(numend)]
for i in range(numend):
direct2=int(random(2)) #0=north<->south, 1=east<->west
xloc2=int(random(1,m))
yloc2=int(random(1,m))
a2=int(random(m-1))
b2=int(random(m-1))
while (xloc1==xloc2 and a1==a2) or (yloc1==yloc2 and b1==b2):
direct2=int(random(2)) #0=north<->south, 1=east<->west
xloc2=int(random(1,m))
yloc2=int(random(1,m))
a2=int(random(m-1))
b2=int(random(m-1))if direct2==0:
x2[i]=xloc2*(blocksize+roadwidth)+roadwidth/2
y2[i]=a2*(blocksize+roadwidth)+int(random(blocksize))+roadwidth
runx[i]=x2[i]
runy[i]=y2[i]
else:
x2[i]=b2*(blocksize+roadwidth)+int(random(blocksize))+roadwidth
y2[i]=yloc2*(blocksize+roadwidth)+roadwidth/2
runx[i]=x2[i]
runy[i]=y2[i]
global index, optimal, last, weight
index = [0 for i in range(m**2+1+numend)] #determine if the best path from point i to starting point is found. 0=no, 1=yes
optimal = [9999.99 for i in range(m**2+1+numend)] #length of the best path
last = [0 for i in range(m**2+1+numend)] #last crossing in the best path
weight = [[9999.99 for x in range(m**2+1+numend)] for y in range(m**2+1+numend)]
#determine weight for each road section
for i in range(n):
for j in range(m):
weight[i*m+j+1][(i+1)*m+j+1]=(random(1,10))
weight[(i+1)*m+j+1][i*m+j+1]=weight[i*m+j+1][(i+1)*m+j+1]
weight[j*m+i+1][j*m+i+2]=(random(1,10))
weight[j*m+i+2][j*m+i+1]=weight[j*m+i+1][j*m+i+2]
global X, Y
X=[[0 for i in range(m)] for j in range(m)]
Y=[[0 for i in range(m)] for j in range(m)]
for i in range(m):
for j in range(m):
X[i][j]=j*(blocksize+roadwidth)+roadwidth/2
Y[i][j]=i*(blocksize+roadwidth)+roadwidth/2
if X[i][j]==x1 and (y1-Y[i][j])>0 and (y1-Y[i][j])<(blocksize+roadwidth/2):
weight[0][i*m+j+1]=weight[i*m+j+1][(i+1)*m+j+1]/(blocksize+roadwidth)*(y1-Y[i][j])
weight[0][(i+1)*m+j+1]=weight[i*m+j+1][(i+1)*m+j+1]-weight[0][i*m+j+1]
weight[i*m+j+1][0]=weight[0][i*m+j+1]
weight[(i+1)*m+j+1][0]=weight[0][(i+1)*m+j+1]
for ii in range(numend):
if X[i][j]==x2[ii] and (y2[ii]-Y[i][j])>0 and (y2[ii]-Y[i][j])<(blocksize+roadwidth/2):
weight[m*m+1+ii][i*m+j+1]=weight[i*m+j+1][(i+1)*m+j+1]/(blocksize+roadwidth)*(y2[ii]-Y[i][j])
weight[m*m+1+ii][(i+1)*m+j+1]=weight[i*m+j+1][(i+1)*m+j+1]-weight[m*m+1+ii][i*m+j+1]
weight[i*m+j+1][m*m+1+ii]=weight[m*m+1+ii][i*m+j+1]
weight[(i+1)*m+j+1][m*m+1+ii]=weight[m*m+1+ii][(i+1)*m+j+1]
if Y[i][j]==y1 and (x1-X[i][j])>0 and (x1-X[i][j])<=(blocksize+roadwidth/2):
weight[0][i*m+j+1]=weight[i*m+j+1][i*m+j+2]/(blocksize+roadwidth)*(x1-X[i][j])
weight[0][i*m+j+2]=weight[i*m+j+1][i*m+j+2]-weight[0][i*m+j+1]
weight[i*m+j+1][0]=weight[0][i*m+j+1]
weight[i*m+j+2][0]=weight[0][i*m+j+2]
for ii in range(numend):
if Y[i][j]==y2[ii] and (x2[ii]-X[i][j])>0 and (x2[ii]-X[i][j])<(blocksize+roadwidth/2):
weight[m*m+1+ii][i*m+j+1]=weight[i*m+j+1][i*m+j+2]/(blocksize+roadwidth)*(x2[ii]-X[i][j])
weight[m*m+1+ii][i*m+j+2]=weight[i*m+j+1][i*m+j+2]-weight[m*m+1+ii][i*m+j+1]
weight[i*m+j+1][m*m+1+ii]=weight[m*m+1+ii][i*m+j+1]
weight[i*m+j+2][m*m+1+ii]=weight[m*m+1+ii][i*m+j+2]
weight[0][0]=0
for ii in range(numend):
weight[m*m+1+ii][m*m+1+ii]=0
# Dijkstra Algorithm
global minimum, mini
index[0]=1
optimal[0]=0 #i=0 represents starting point
for k in range(m**2+1+numend):
for i in range(m**2+1+numend):
if index[i]==1:
for j in range(m**2+1+numend):
if index[j]==0:
if optimal[i]+weight[i][j]<optimal[j]:
optimal[j]=optimal[i]+weight[i][j]
last[j]=i
minimum=9999.99
mini=0
for i in range(m**2+1+numend):
if index[i]==0 and optimal[i]<minimum:
minimum=optimal[i]
mini=i
index[mini]=1
#verify
print weight
print index
print X
print Y
print optimal
print last
def draw():
clear()
background(0)
#building the neighborhood
for i in range(roadwidth,width,blocksize+roadwidth):
for j in range(roadwidth,width,blocksize+roadwidth):
fill(50)
stroke(0)
strokeWeight(3)
rect(i,j,blocksize,blocksize)
for i in range(n):
for j in range(m):
if weight[i*m+j+1][(i+1)*m+j+1]<5:
r= (weight[i*m+j+1][(i+1)*m+j+1]-1)/4*255
g=255
b=0
else:
r=255
g=255-( weight[i*m+j+1][(i+1)*m+j+1]-5)/5*255
b=0
fill(r,g,b,150)
noStroke()
rect(X[i][j]-20,Y[i][j]+25,40,150)
#fill(0)
#myfont=createFont("Arial",30)
#textFont(myfont)
#text( weight[i*m+j+1][(i+1)*m+j+1],X[i][j]-20,Y[i][j]+100)
if weight[j*m+i+1][j*m+i+2]<5:
r=( weight[j*m+i+1][j*m+i+2])/4*255
g=255
b=0
else:
r=255
g=255-( weight[j*m+i+1][j*m+i+2]-5)/5*255
b=0
fill(r,g,b,150)
noStroke()
rect(X[j][i]+25,Y[j][i]-20,150,40)
#fill(0)
#myfont=createFont("Arial",30)
#textFont(myfont)
#text(weight[j*m+i+1][j*m+i+2],X[j][i]+100,Y[j][i])
#draw the optimal path
global p, q,minimum2
for ii in range(numend):
p=m*m+1+ii
q=last[p]
stroke(255,255,255)
strokeWeight(3)
line(x2[ii]-10+ii*20/numend,y2[ii]-10+ii*20/numend,X[int((q-1)/m)][int((q-1)%m)]-10+ii*20/numend,Y[int((q-1)/m)][int((q-1)%m)]-10+ii*20/numend)
if runx[ii]==x2[ii] and runx[ii]==X[int((q-1)/m)][int((q-1)%m)]:
if ((runy[ii]-y2[ii])*(runy[ii]-Y[int((q-1)/m)][int((q-1)%m)])<0) or (runy[ii]==y2[ii]):
fill(255,0,0)
strokeWeight(0)
ellipse(runx[ii]-10+ii*20/numend,runy[ii]-10+ii*20/numend,20,20)
spd[ii]=(Y[int((q-1)/m)][int((q-1)%m)]-y2[ii])/(optimal[p]-optimal[q])*spdctrl
if (runy[ii]+spd[ii]-y2[ii])*(runy[ii]+spd[ii]-Y[int((q-1)/m)][int((q-1)%m)])>0:
spd[ii]=Y[int((q-1)/m)][int((q-1)%m)]-runy[ii]
runy[ii]=runy[ii]+spd[ii]
if runy[ii]==y2[ii] and runy[ii]==Y[int((q-1)/m)][int((q-1)%m)]:
if (runx[ii]-x2[ii])*(runx[ii]-X[int((q-1)/m)][int((q-1)%m)])<0 or runx[ii]==x2[ii]:
fill(255,0,0)
strokeWeight(0)
ellipse(runx[ii]-10+ii*20/numend,runy[ii]-10+ii*20/numend,20,20)
spd[ii]=(X[int((q-1)/m)][int((q-1)%m)]-x2[ii])/(optimal[p]-optimal[q])*spdctrl
if (runx[ii]+spd[ii]-x2[ii])*(runx[ii]+spd[ii]-X[int((q-1)/m)][int((q-1)%m)])>0:
spd[ii]=X[int((q-1)/m)][int((q-1)%m)]-runx[ii]
runx[ii]=runx[ii]+spd[ii]
p=q
q=last[p]
while q<>0:
stroke(255,255,255)
strokeWeight(3)
line(X[int((p-1)/m)][int((p-1)%m)]-10+ii*20/numend,Y[int((p-1)/m)][int((p-1)%m)]-10+ii*20/numend,X[int((q-1)/m)][int((q-1)%m)]-10+ii*20/numend,Y[int((q-1)/m)][int((q-1)%m)]-10+ii*20/numend)
if runx[ii]==X[int((p-1)/m)][int((p-1)%m)] and runx[ii]==X[int((q-1)/m)][int((q-1)%m)]:
if (runy[ii]-Y[int((p-1)/m)][int((p-1)%m)])*(runy[ii]-Y[int((q-1)/m)][int((q-1)%m)])<0 or runy[ii]==Y[int((p-1)/m)][int((p-1)%m)]:
fill(255,0,0)
strokeWeight(0)
ellipse(runx[ii]-10+ii*20/numend,runy[ii]-10+ii*20/numend,20,20)
spd[ii]=(Y[int((q-1)/m)][int((q-1)%m)]-Y[int((p-1)/m)][int((p-1)%m)])/(optimal[p]-optimal[q])*spdctrl
if (runy[ii]+spd[ii]-Y[int((p-1)/m)][int((p-1)%m)])*(runy[ii]+spd[ii]-Y[int((q-1)/m)][int((q-1)%m)])>0:
spd[ii]=Y[int((q-1)/m)][int((q-1)%m)]-runy[ii]
runy[ii]=runy[ii]+spd[ii]
if runy[ii]==Y[int((p-1)/m)][int((p-1)%m)] and runy[ii]==Y[int((q-1)/m)][int((q-1)%m)]:
if (runx[ii]-X[int((p-1)/m)][int((p-1)%m)])*(runx[ii]-X[int((q-1)/m)][int((q-1)%m)])<0 or runx[ii]==X[int((p-1)/m)][int((p-1)%m)]:
fill(255,0,0)
strokeWeight(0)
ellipse(runx[ii]-10+ii*20/numend,runy[ii]-10+ii*20/numend,20,20)
spd[ii]=(X[int((q-1)/m)][int((q-1)%m)]-X[int((p-1)/m)][int((p-1)%m)])/(optimal[p]-optimal[q])*spdctrl
if (runx[ii]+spd[ii]-X[int((p-1)/m)][int((p-1)%m)])*(runx[ii]+spd[ii]-X[int((q-1)/m)][int((q-1)%m)])>0:
spd[ii]=X[int((q-1)/m)][int((q-1)%m)]-runx[ii]
runx[ii]=runx[ii]+spd[ii]
p=q
q=last[p]
stroke(255,255,255)
strokeWeight(3)
line(X[int((p-1)/m)][int((p-1)%m)]-10+ii*20/numend,Y[int((p-1)/m)][int((p-1)%m)]-10+ii*20/numend,x1-10+ii*20/numend,y1-10+ii*20/numend)
if runx[ii]==X[int((p-1)/m)][int((p-1)%m)] and runx[ii]==x1:
if (runy[ii]-Y[int((p-1)/m)][int((p-1)%m)])*(runy[ii]-y1)<0 or runy[ii]==Y[int((p-1)/m)][int((p-1)%m)]:
fill(255,0,0)
strokeWeight(0)
ellipse(runx[ii]-10+ii*20/numend,runy[ii]-10+ii*20/numend,20,20)
spd[ii]=(y1-Y[int((p-1)/m)][int((p-1)%m)])/(optimal[p]-optimal[0])*spdctrl
if (runy[ii]+spd[ii]-Y[int((p-1)/m)][int((p-1)%m)])*(runy[ii]+spd[ii]-y1)>0:
spd[ii]=y1-runy[ii]
runy[ii]=runy[ii]+spd[ii]
if runy[ii]==Y[int((p-1)/m)][int((p-1)%m)] and runy[ii]==y1:
if (runx[ii]-X[int((p-1)/m)][int((p-1)%m)])*(runx[ii]-x1)<0 or runx[ii]==X[int((p-1)/m)][int((p-1)%m)]:
fill(255,0,0)
strokeWeight(0)
ellipse(runx[ii]-10+ii*20/numend,runy[ii]-10+ii*20/numend,20,20)
spd[ii]=(x1-X[int((p-1)/m)][int((p-1)%m)])/(optimal[p]-optimal[0])*spdctrl
if (runx[ii]+spd[ii]-X[int((p-1)/m)][int((p-1)%m)])*(runx[ii]+spd[ii]-x1)>0:
spd[ii]=x1-runx[ii]
runx[ii]=runx[ii]+spd[ii]
if runx[ii]==x1 and runy[ii]==y1:
runx[ii]=x2[ii]
runy[ii]=y2[ii]
fill(0,0,255)
strokeWeight(0)
ellipse(x1,y1,30,30)
fill(255,255,0)
strokeWeight(0)
ellipse(x2[ii]-10+ii*20/numend,y2[ii]-10+ii*20/numend,20,20)
'''
x3=0.00
y3=0.00
x3=mouseX
y3=mouseY
minimum2=9999.99
i=int(x3/200)
if i==5:
i=4
j=int(y3/200)
if j==5:
j=4
if sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]<minimum2:
minimum2=sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]
mini=j*m+i+1
j=j+1
if sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]<minimum2:
minimum2=sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]
mini=j*m+i+1
i=i+1
if sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]<minimum2:
minimum2=sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]
mini=j*m+i+1
j=j-1
if sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]<minimum2:
minimum2=sqrt((x3-X[j][i])**2+(y3-Y[j][i])**2)/70+optimal[j*m+i+1]
mini=j*m+i+1
stroke(255,255,255)
strokeWeight(5)
q=mini
line(x3,y3,X[int((q-1)/m)][int((q-1)%m)],Y[int((q-1)/m)][int((q-1)%m)])
p=q
q=last[p]
while q<>0:
line(X[int((p-1)/m)][int((p-1)%m)],Y[int((p-1)/m)][int((p-1)%m)],X[int((q-1)/m)][int((q-1)%m)],Y[int((q-1)/m)][int((q-1)%m)])
p=q
q=last[p]
line(X[int((p-1)/m)][int((p-1)%m)],Y[int((p-1)/m)][int((p-1)%m)],x1,y1)
fill(0,0,255)
strokeWeight(0)
ellipse(x1,y1,30,30)
fill(255,255,0)
strokeWeight(0)
ellipse(x3,y3,20,20)
Reference:
Ettema, Dick, and Roy Nieuwenhuis. 2017. Residential Self-Selection and Travel Behaviour: What Are the Effects of Attitudes, Reasons for Location Choice and the Built Environment? Journal of Transport Geography 59: 146–155.
Fishwick, P. A. 1995. Simulation Model Design and Execution: Building Digital Worlds. PrenticeHall. H
Jin Joo Lee and Paul A. Fishwick. 1995. SIMULATION-BASED REAL-TIME DECISION MAKING FOR ROUTE PLANNING
Ge, Jiaqi, and J. Gary Polhill. 2016. Exploring the Combined Effect of Factors Influencing Commuting Patterns and CO2 Emissions in Aberdeen Using an Agent-Based Model. Journal of Artificial Societies and Social Simulation 19(3). https://EconPapers.repec.org/RePEc:jas:jasssj:2015-122-3.
Kang, Hyun Gu, and Jonathan B. Dingwell. 2008. Separating the Effects of Age and Walking Speed on Gait Variability. Gait & Posture 27(4): 572–577.
Li, Jianling. 2018. Residential and Transit Decisions: Insights from Focus Groups of Neighborhoods around Transit Stations. Transport Policy 63: 1–9.
Lovasi, Gina S., Anne V. Moudon, Amber L. Pearson, et al. 2008. Using Built Environment Characteristics to Predict Walking for Exercise. International Journal of Health Geographics 7: 10.
