Tôi đã viết ứng dụng bản đồ năm 18 tuổi như thế nào
Map
2
google maps api
2
White

Nghiêm Tiến Viễn viết ngày 29/06/2020

Map
Hồi đó tôi mới 12, năm cuối cấp thi đại học đến đít rồi còn bày đặt viết ứng dụng bản đồ. Giờ nghĩ lại thì vẫn thấy đó là ứng dụng tôi tự hào nhất. Lúc đó Google map còn chưa được chi tiết như bây giờ, tp Vinh của tôi trên đó vẫn còn sơ khai lắm. Có một ứng dụng bản đồ VN cũng vừa ra mắt ở thời điểm ấy là 1650km.com . Theo như trang web đấy thì 1650km là số km bờ biển VN — tên ý nghĩa phết. Thấy thích nên tôi cũng muốn thử tự mình làm một ứng dụng bản đồ.

Hồi đó tôi thi tin học trẻ không chuyên, năm trước đó tôi đã được giải nhất tỉnh và giải 3 toàn quốc gì đó về làm phần mềm. Giải tin học trẻ không chuyên thường có 2 hệ thống giải, 1 dành cho thi lập trình và 1 dành cho phần mềm. Tôi chọn thi phần mềm vì 2 lý do Ít cạnh tranh và thời gian chuẩn bị dài — khôn thế chứ lị. Với phần mềm bản đồ này, tôi đã nghĩ đến việc đạt tiếp giải năm nay. Lúc đó, tôi sẽ nói với ban giám khảo rằng, tại sao tôi đặt tên phần mềm là Vimap ? Vì ban đầu, nó là bản đồ thành phố Vinh, lớn hơn nữa nó sẽ là bản đồ Việt Nam, lớn hơn nữa nữa nó sẽ là bản đồ của Viễn — tên tui :P Tiếc là cái giây phút đó chỉ có trong tưởng tượng của chàng trai 18 tuổi thôi.

Tưởng tượng chán rồi bắt tay vào làm thôi. Đầu tiên là phải vẽ bản đồ. Tôi ra nhà sách, mua 1 tấm bản đồ của thành phố về. Bản đồ giấy nên to dễ sợ. Tôi mang ra tiệm scan để scan lên máy tính, người ta phải scan nhiều lần, mỗi lần 1 góc rồi tôi copy về. Về nhà hì hụi dùng photoshop để ghép nó lại với nhau, dùng Pen vẽ lại từng con đường, từng góc phố. Tô màu xám-vàng giống như google map. Hồi đó chưa biết đồ họa vector nên làm bitmap thôi. Để làm tính năng zoom-in zoom-out, tôi tự phóng to, thu nhỏ bản đồ rồi lưu ra các file khác nhau. Vì bản đồ nó rất to nên không thể lưu 1 file ảnh được, lưu vậy lúc người dùng load được cái ảnh chắc mất nguyên năm. Cái này đương nhiên học tập Google map, tôi thấy nó load ảnh theo từng ô vuông. Từ cái bản đồ to, tôi chia nhỏ thành nhiều ô vuông khác nhau, mỗi ô vuông là 1 file. May là Photoshop nó có tính năng này, chứ ko thì mệt chết bà.

Có bản đồ xong, tôi viết các tính năng kéo thả để di chuyển bản đồ, zoom.. Tất cả viết bằng HTML, JS, CSS. Phần này chỉ có to tay thôi chứ không cần suy nghĩ nhiều. Phần khó nhất là phần tìm đường. Người dùng chọn 2 điểm trên bản đồ, giờ làm sao để tìm đường đi ngắn nhất giữa 2 điểm đó — đây cũng là phần tôi tự hào nhất.

Hồi đó tôi thích tin nhưng thi chuyên Tin không đậu, may là còn đậu chuyên Lý. Do không theo chuyên Tin nên mấy cái thuật toán tôi đều tự học, chủ yếu là đọc tài liệu trên mạng hoặc lên mấy diễn đàn như ddth.com để hỏi. Các thuật toán tìm đường thì trong sách Toán rời rạc có, cũng ngâm cứu chán chê mà chưa chọn được cách nào ưng ý để áp dụng vào thực tế. Trong thời gian nghiên cứu thuật toán tìm đường, tôi chuyển sang việc nhập liệu trước.
Đầu tiên là khai báo các con đường trong thành phố. Tôi tạo 1 trang riêng dành cho người quản trị để nhập liệu. Với mỗi con đường, tôi chọn các điểm nằm trên con đường đó bằng cách click lên bản đồ. Mỗi điểm mới sẽ nối với điểm cũ bằng đoạn thẳng, một con đường sẽ bao gồm nhiều đoạn thẳng gấp khúc như vậy. Mình lưu trữ trong db như sau

  • name : "Pham Hong Thai"
  • points : "x1*y1|x2*y2|x3*y3"

Hồi đó dùng MySql để lưu trữ. x1,y1 là tọa độ điểm 1, các điểm cách nhau bằng dấu gạch đứng | và lưu hết các điểm vào trong 1 trường. Các bạn đừng chửi ngu nhé vì 12 năm trước thì cũng chỉ đến thế là cùng thôi :D
Nhập liệu xong thì ngon rồi, tìm kiếm tên đường cái là hiện lên màn hình, vẽ đường đi từ đầu đến cuối đường. Hồi đó dùng thư viện vẽ hình gì mà nó cũng chỉ dùng html thôi ấy. 1 đoạn thẳng của nó là bao gồm nhiều div chồng lên nhau như pixel, cho nên đoạn thẳng vẽ ra nó răng cưa chứ không được mềm mại. Hồi đó cũng cố tìm rồi nhưng không tìm được thư viện nào khác.

Quay lại bài toán tìm đường, tôi quyết định chọn thuật toán A*. Hồi đó chỉ tìm hiểu thuật toán này qua Wikipedia. Ngâm cứu mãi rồi bắt tay vào viết, nhưng thực ra viết xong rồi cũng ko biết mình hiểu có đúng thuật toán hay không :D Để hiểu A* thì các bạn phải đọc về thuật toán tìm Dijkstra trước, xong rồi đọc tiếp các thuật toán tối ưu dùng hàm heuristic.

Cơ bản các bạn có thể hiểu như này, trường hợp tệ nhất của mọi thuật toán tìm kiếm là Vét cạn — tức là thử tất cả các trường hợp có thể. Trong tìm đường thì Vét cạn là thử tất cả các cung đường có thể đi, sau đó chọn ra đường ngắn nhất. Để giảm số lượng cung đường cần thử, người ta đưa vào các hàm đánh giá heuristic. Giả sử ta đang ở ngã 3 đường, giờ chọn rẽ phải hay rẽ trái ? Hàm heuristic sẽ dựa vào các thông số đã biết để đưa ra quyết định là rẽ bên nào sẽ có khả năng về đích sớm hơn.

Tôi lúc đó hiểu A* một cách hình tượng như thế này : Bạn đang cần tìm đường đến đài truyền hình của thành phố. Tuy bạn đang ở xa nhưng bạn vẫn nhìn thấy tháp truyền hình. Bạn vừa di chuyển vừa nhìn ngọn tháp để đưa ra phán đoán. Bạn sẽ chọn ngã rẽ nào đưa bạn đến gần ngọn tháp hơn. Cách hiểu này rất hợp lý trong thực tế và cũng phù hợp với việc tìm đường đi trên bản đồ thành phố.

Áp dụng cụ thể như sau. Giả sử bạn xuất phát ở điểm A(x1,y1) Điểm này nối với điểm B(x2,y2) và điểm C(x3,y3). Điểm đích là điểm D(x4, y4). Bạn sẽ chọn điểm nào để rẽ ? Đầu tiên chúng ta tính khoảng cách AB và AC là đường đi trên thực tế, sau đó tính khoảng cách BD và CD ( đây là khoảng cách đường chim bay — chứ trên thực tế chưa chắc B và D được nối với nhau trực tiếp ). Kế tiếp chúng ta so sánh, nếu AB+BD < AC+CD thì điểm B sẽ tiềm năng hơn điểm C — do đưa chúng ta đến gần điểm đích hơn, và do đó chúng ta bổ sung điểm B vào đường đi.
Giống như các thuật toán loang khác ( tìm theo chiều rộng, chiều sâu ) chúng ta phải lưu vết những con đường đang đi dở để quay lui khi hàm đánh giá cho biết rằng chúng ta đang đi xa điểm đích. VD trong trường hợp sau

  • Từ nút gốc A, chúng ta bổ sung 2 điểm tiềm năng là B và C vào thành nút lá. Ta thấy AB+BD < AC+CD , do đó chúng ta chọn điểm B là điểm phát triển tiếp đường đi.
  • Bước 2, từ B, chúng ta chỉ có 1 đường đi là tới E.
  • Bước 3, chúng ta tính từ 2 điểm lá là C và E, ta thấy AC+CD<AB+BE+ED, lúc này đường đi qua C lại tiềm năng hơn, do đó ta chọn C để đi.
  • Bước 4, từ C chúng ta đi đến F.
  • Bước 5, từ 2 điểm lá là E và F, chúng ta thấy AC+CF+FD<AB+BE+ED, do đó chúng ta chọn F là bước đi tiềm năng.
  • Từ F, chúng ta tìm đến D => Tìm ra đường.

Tư tưởng là vậy nhưng để cài đặt thuật toán chạy thành công thì cũng phải mất kha khá thời gian. Và với một người không chuyên thì nó là một điều đáng tự hào. Tôi đã hoàn thành bản đồ thành phố với các chức năng cơ bản là kéo thả, phóng to thu nhỏ, tìm tên đường và tìm đường đi giữa 2 điểm. Mặc dù vậy, sản phẩm này chỉ đạt giải 2 cuộc thi Tin học trẻ không chuyên cấp Tỉnh và không được tham gia cuộc thi toàn quốc. Nhưng không vì thế mà tôi dừng lại, tôi và một số bạn đã liên hệ với tỉnh đoàn Nghệ An để đưa bản đồ này vào phục vụ cho mùa thi. Lúc đấy đã đặt domain là vinhmuathi.net. Hồi đấy Vinh là một điểm thi tập trung, nên các thí sinh từ các tỉnh lân cận đổ về Vinh để thi. Chúng tôi đưa danh sách nhà trọ và các điểm thi lên bản đồ để phục vụ các bạn ở xa. Mặc dù năm đó chúng tôi cũng đi thi :P May mà đỗ.

Lúc mới làm xong, tôi có đăng lên ddth, giờ vẫn còn xem lại được ở đây https://www.ddth.com/showthread.php/174454-B%E1%BA%A3n-%C4%91%E1%BB%93-TP-Vinh-tr%E1%BB%B1c-tuy%E1%BA%BFn?s=aeb9916ba7f4b9ecbe98997c3cf668c7 . Nhờ bài đăng này mà tôi được các anh ở Naiscorp (socbay) tài trợ hosting, từ đó làm quen được với các anh nên sau này đi đại học được nâng đỡ nhiều. Cũng nhờ thời gian thực tập-làm việc ở Naiscorp nên tôi mới được trải qua nhiều thứ như bây giờ.

Tiếc là vào năm nhất đại học, tôi đổi máy tính qua lại, rồi do bất cẩn mà tôi làm mất toàn bộ mã nguồn Vimap. Giờ tiếc quá, cũng không còn cái ảnh screenshot nào. Nên bài này phải ngồi viết chay như này, sợ sau này cũng quên mất. Nghĩ lại thì hồi cấp 3 là thời gian được làm theo sở thích của mình nhiều nhất. Bạn có thể theo đuổi nhiều ngày nhiều tháng vì đam mê mà không hề có áp lực gì. Vậy nên các bạn cấp 3 hãy tận hưởng nhé ./

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Nghiêm Tiến Viễn

4 bài viết.
9 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
7 3
Livestream đã và đang là chuyện hằng ngày hằng giờ trên các mạng xã hội. Những bài viết livestream được ưu tiên hiển thị nhiều hơn so với những bài...
Nghiêm Tiến Viễn viết hơn 3 năm trước
7 3
White
7 3
Đây là kinh nghiệm của mình gần đây, khi server bị hack và mình vất vả chống đỡ. Bài ghi lại cách cấu hình server CentOS cho bảo mật hơn. Cấu hìn...
Nghiêm Tiến Viễn viết hơn 2 năm trước
7 3
White
3 0
Sau 1 thời gian làm ReactJS cho website gostream.co thì nhu cầu tất yếu tiếp theo là làm app. Mặc dù GoStream đã có app cả ios và android nhưng app...
Nghiêm Tiến Viễn viết hơn 1 năm trước
3 0
Bài viết liên quan
White
17 8
Đây là một câu hỏi thường gặp trong những buổi phỏng vấn ứng viên Java, và cũng có không ít bạn vì câu hỏi này mà gặp trắc trở, hôm nay chúng ta sẽ...
Hoàng Nguyễn viết gần 5 năm trước
17 8
White
1 0
Trong một số ứng dụng sử dụng Google Maps Android API bạn có thể thấy các marker rải trên bản đồ, nhưng với số lượng lớn marker sẽ làm cho trải ngh...
Nguyễn Trọng Công viết 3 năm trước
1 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
4 bài viết.
9 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!